From dik@cwi.nl Tue Jan 10 18:20:52 1995 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA28829; Tue, 10 Jan 95 18:20:52 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Wed, 11 Jan 1995 00:09:41 +0100 Received: by boring.cwi.nl id ; Wed, 11 Jan 1995 00:09:40 +0100 Date: Wed, 11 Jan 1995 00:09:40 +0100 From: Dik.Winter@cwi.nl Message-Id: <9501102309.AA08275=dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu, txr@alumni.caltech.edu 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.