> < ^ From:

< ^ Subject:

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

> < [top]