Worst case scenario

Thought some peeps might like some worst case scenarios

I wrote a little script that works out every permutation of a stack

Below are 3 of the 455 stacks that take 9 flips to solve for an 8 disc stack - sort of puts paid to those claims of 'I can do it in N-1' !

I ain't running this with any more than 8 discs 'cos this run took 14Mb and 10:52:30 to complete - 9 would take weeks...

1-3-2-4-6-8-5-7
6-8-4-2-7-5-8-6
7-1-4-2-6-8-3-5

I once thought I had proved mathematically that it was possible to solve any and all of these problems in N-1. The problem was finding the algorithm.

I'll look and see...

Mean while, a quick question: Does your "Every possible permutation" allow for duplicate flips? Example:

[pre]
Step: 1-2-3-4
3 7 8 7
7 3 3 3
8 8 7 8
[/pre]

You see, even though this is "a" possible 4th level permutation, the stack is still solvable with 1 flip... I will check my research again, but if I remember correctly, after N-1 permutations, everything was a duplicate from some past permutation.

1 3 2 1 7 5 6 8 1
3 1 1 2 5 7 8 7 2
2 2 3 3 8 8 7 6 3
4 4 4 4 6 6 5 5 4
6 6 6 6 4 4 4 4 5
8 8 8 8 3 3 3 3 6
5 5 5 5 2 2 2 2 7
7 7 7 7 1 1 1 1 8

Is this the solution? If not, could you post the solution - Shouldn't there only be one optimum solution?

Heh - proof by example - 9 is _not_ the optimum solution

Stacks are vertical:

6 8 4 7 5 8 6 2
8 5 2 2 4 8 6 4
4 7 7 4 2 7 5 5
2 2 5 5 7 2 4 6
7 4 8 8 8 4 2 6
5 8 8 8 8 5 7 7
8 6 6 6 6 6 8 8
6 6 6 6 6 6 8 8

As posted before on the forum:

5,3,6,1,4,2 has a solution of 7.

That should get all of you thinking "I can do it in N-1" to think again. (And I have tested all permutation of 6 numbers, and worst case is 7. I have also tested all permutation of 7..)