From:

~~~ Subject:

in an earlier message, i promised to pass along any information

i obtained about progress on the upper bound for the length of

god's algorithm. i've received a copy of the article "rubik's

cube in 42 moves" by hans kloosterman, which i summarize below.

first here are some caveats:

* i haven't verified this algorithm.

* throughout, `move' refers to any turn of a single face.

i don't know what bound is achieved in the quarter-turn metric.

* it may be the case that this algorithm has been improved.

please let me (and cube-lovers) know if you have more information.

"rubik's cube in 42 moves" by hans kloosterman

the algorithm used here is a slight variant of thistlethwaite's

algorithm. we work through a chain of subgroups:

G_0 = < F, B, L, R, U, D > ( full group ) G_1 = < F2, B2, L, R, U, D > G_2 = < F2, B2, L2, R2, U, D > G_3 = subgroup of G_2 in which all U-cubies are in the U face (thus all D-cubies are in the D face and all U-D slice cubies are in the U-D slice) G_4 = { 1 }.

there are four stages: stage i reduces our pattern from G_{i-1} to G_i.

the indices of the subgroups are:

( G_0 : G_1 ) = 2048 = 2^11 ( G_1 : G_2 ) = 1082565 = 3^9 * 5 * 11 ( G_2 : G_3 ) = 4900 = 2^2 * 5^2 * 7^2 ( G_3 : G_4 ) = 3981310 = 2^14 * 3^5

the maximum number of moves in the stages are 7, 10, 8 and 18

respectively, for a maximum total of 43 moves. however, in

the worst-case scenario of stages 3 and 4, it was checked that

no position actually required 26 moves; i.e. we can arrange a

cancellation between the two stages. thus stages 3 and 4

together require 25 moves at most, which gives the final

figure of 42 moves.

it seems to me that a lot of work was done on an algorithm

for restoring the "magic domino" (the 2x3x3 puzzle), and

these results were applied to stages 3 and 4.

mike