John Pliam wrote in his article of 1995/10/12
I saw this on the Gap forum and was wondering what
is the worst case minimum # of moves (diameter of the Cayley graph)?
Does anyone know? I have read claims of like 50?
I have become interested in this again, because of applications to routing
in parallel archectures (I actually found papers using the Schreier thm.
in eng. journals :-)
I assume you mean God's algorithm for Rubik's Cube. I.e., how many
quarter turns would God have to make to bring a state back to the solved
state in the worst case?
We know now that there are states (e.g. the superflip where all edges are
flipped and all corners are correct) that require at least 24 quarter
turns. This was done basically as follows. Enumerate all states that
are at most 11 quarter turns from the solved state. Then enumerate all
states that are at most 11 quarter turns away from the superflip state.
Those two sets have no common element, so superflip is more than 22
quarter turns away from the solved state. Since it is an even
permutation, any process for the superflip requires an even number of
quarter turns. Thus superflip is at least 24 quarter turns away from the
solved state. This was done by Jerry Bryan. Michael Reid found a
process for the superflip that requires 24 quarter turns.
On the other hand we know an algorithm that requires at most 42 quarter
turns for any state. This works by first bringing the state into the
subgroup H = < U, D, L^2, R^2, F^2, B^2 >, and then solving this state.
Both the coset space G / H and H were exhaustively searched (quite an
achievement). This was done by Michael Reid.
The agreement seems to be that the true answer will be very close to 24.
So I don't think anybody is working on raising the lower bound.
I don't think anybody has an idea how to lower the upper bound much.
You can find out more about this and about the Cube in general by
joining the Cube-Lovers mailing list. To subscribe send a message
to 'Cube-Lovers-Request@ai.mit.edu'. To read older messages get the
archives from 'ftp.ai.mit.edu:/pub/cube-lovers/' or check out
-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany