> < ^ From:

> < ^ Subject:

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

'http://www.math.rwth-aachen.de:8000/LDFM/People/Martin_Schoenert_Private/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]