[next] [prev] [up] Date: Wed, 11 Jan 95 00:09:40 +0100
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
[next] [prev] [up] Subject: Re: kociemba's algorithm for quarter turns

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.

[next] [prev] [up] [top] [help]