Dik.Winter@cwi.nl writes:
>But it can take long.
Note the word *long*. There is a 20-turn sequence for superflip. I have tried for shorter sequences using Kociemba's algorithm. (The 20-turn sequence does not take so awfully long to find, something like a day on this machine * perhaps). I started the program 12 November 1993 at 12:03. At 11 December 11:58 it had searched phase1 up to length 16. Alas, the machine crashed on 16 December 22:14. The problem is the awfully large number of solutions that come out of phase 1 and that have to be checked &. To wit: Length phase 1 number complete solutions 8 0 9 0 10 3072 L=23, L=22 11 61568 L=21 12 792256 13 8695488 L=20 14 87912832 15 841171136 16 7765525280 % The following solutions were successively found: L=23: F1 B1 R1 F2 R2 U3 D1 F1 R1 L1 B2 D1 F2 B2 D3 B2 D1 B2 U2 R2 B2 D1 B2 L=22: F1 B1 R1 F2 R2 U3 D1 F1 R3 L1 U1 R2 F2 D3 B2 D3 R2 L2 U3 F2 D2 L2 L=21: F1 B1 R1 U2 B2 U3 D3 R2 B3 R1 L1 U1 F2 L2 D2 B2 D3 F2 D1 L2 D1 L=20: F1 B1 U2 R1 F2 R2 B2 U3 D1 F1 U2 R3 L3 U1 B2 D1 R2 U1 B2 U1
So the next step is 17 in phase 1 with at most 2 turns in phase 2. I will
start the program again sometime.
So we find more than a month for a single configuration. And for this
we need not check neighbors as the configuration is at a local maximum.
I have another file with longuish configuration. That is from a period
when I tried random configurations, the results were:
turns #conf
16 1
17 24
18 248
19 1429
20 8481
total 10183
This has also taken an awfully long time to do (I think it was about 2
months). I let the program stop as soon as it had found a solution of
20 turns or less. All random configurations were solved, but many of
the 20 turn configurations have shorter solutions.
So yes, it can be done, but:
> 5) Give up when patience is exhausted.
this will come up before anything useful can be concluded I think.
Unless something can be done to reduce the numbers. It is possible
because there are configurations that will come up many times during
the process, but I do not yet know what to do about that within a
reasonable amount of memory.
--
* The machine is one processor of a Cray SMP: a 66 MHz Sparc.
& The number is much larger than what I found with other configurations,
for 15 turns about 800 times as large as the second largest.
% Estimated, there was overflow. It can be off an integer
multiple of 4294967296.