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