Istvan T. Hernadvolgyi wrote in his message of 1993/03/28

I am just wondering, if someone could give me a meaningful estimate on
the diameter of the Cayley Graph for the 3x3x3 Rubik's Cube. I know it is
11 for the 2x2x2.

Paul R. Brown replied (and accidently also mailed this reply to the
GAP-Forum, where it was rejected), pointing out that this question only
makes sense when one specifies a set of generators.

Istvan answered in his next message

I am interested in the diameter of the Cayley Graph for the Cube with
the 6 generators that move each face. More specifically, in both cases:
with and without the inverses "allowed" to be in the path.

I don't think anybody looks at Cayley graphs without including inverses
of the generators. If you do this, very unpleasant things happen. For
example, you no longer obtain a measure. Different points in the graph
may have different distances from their antipode(s). And so on.

Lets take the Cayley graph with respect to the 6 quarter turn generators
and their inverses. This is usually called God's algorithm. 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.

Thus we know that the diameter must lie between 24 and 42.
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. On the
other hand, I don't think anybody has an idea how to lower the upper
bound much.

Istvan continued

I would also be interested in the diameter when the generators are the
above mentioned 6, and their pair-wise conjugates.

I don't have the slightest idea.

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

http://WWW.Math.RWTH-Aachen.DE/Private/HomePages/Martin_Schoenert/Cube-Lovers/

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany