~~~ From:

~~~ ~~~ Subject:

I can also report that the superflip requires at least 19 face turns. I

got this result using Shamir's algorithm, which Mike Reid describes briefly

in his message <9412162233.AA27627@ducie.ptc.com>. To repeat him: Shamir's

method allows you to generate in lexicographic order all permutations st,

where s and t are elements of lists S and T of permutations, respectively,

while using only space proportional to the sum of the sizes of the lists.

What I did was to first check that the superflip f couldn't be done in 11 or

fewer face turns (easy) and to then try to solve f=stuv, where s and v have

4 face turns and t and u have 2 to 5 face turns. This is done by scanning

through the (ordered) lists of all st's and all f v^(-1) u^(-1)'s and checking

to see if there is a common element. Shamir's method then has to be applied to

S and T and to V and T, where T is a list of permutations with 2 to 5 face

turns, S is a list of permutations s with 4 face turns, and V is a list of

permutations f v^(-1), where v has 4 face turns. The number of candidates

for s and v can be reduced by making use of the fact that f is central, has

order 2, and is invariant under conjugation by the symmetry group of the cube.

The computation took 52 hours of CPU time on an SGI Crimson (R4000 50/100 MHz

CPU.) More than half the CPU time is spent composing permutations and updating

priority queues (see below.)

Some have expressed concern that Shamir's method is a memory hog. Applying

it to S and T requires a rather complicated tree of permutations in T and a

priority queue of permutations in S. I used the wreath product representation

of the cube group (so `permutation' is something of a misnomer,) and my memory

usage was then as follows:

Per element of S:

48 bytes permutation s in S (can be shared with other S's and T's)

40 bytes composition st (not absolutely necessary, but speeds things up)

16 bytes pointers internal to the queue and to an element t of T

---------

104 bytes

Per element of T: 48 bytes permutation t in T (can be shared, as before) 8 bytes pointer immediately above t <=16 bytes Amortized cost of higher-up regions of the tree ---------- <=72 bytes

The T tree is not altered during traversal, so if you are applying the method

to S and T and V and T simultaneously you just need one T tree.

All told, my memory usage was around 46M.

Looking for a 20 face turn representation by this method would probably take

around 59M of memory and 710 hours of CPU time (on this machine.)

--

David Moews dmoews@xraysgi.ims.uconn.edu