[next] [prev] [up] Date: Fri, 22 May 92 22:56:34 -0700 (PDT)
[next] [prev] [up] From: michael reid <reid@math.berkeley.edu >
~~~ ~~~ [up] Subject: new upper bound

i've managed to reduce the upper bound for the length of god's
algorithm to 39 face turns / 56 quarter turns. we work in three
stages:

1. from  <U, F, R, L, B, D>  to  <U, R, F>
2. from  <U, R, F>           to  <U, R2, F2>
3. from  <U, R2, F2>         to  START

where we're only allowed to use moves that keep us within the
given subgroup.

these three stages were chosen because of the moderate(!) sizes
of the coset spaces that must be considered. the numbers are
253440, 15676416, and 10886400. the maximum number of moves
in each stage was calculated by exhaustively searching the space.

if we count by "face turns," these maximum numbers are 8, 13 and 19.
however, if we make any turns in stage 2, the last such is a quarter
turn of either F or R, and the direction is irrelevant. those
positions at distance 19 in stage 3 (only 24 in all) were checked
to see that they may be solved in 19 face turns starting with
either F2 or R2. therefore we can arrange to combine the last
move of stage 2 with the first move of stage 3 in the event that
we must make the maximal number of moves in each stage. this
gives the final figure of 39 face turns.

if we count by "quarter turns," the maximum numbers are 9, 16 and 33.
this time, those configurations at distance either 32 or 33 in stage 3
(only 10 and 4 positions, respectively) were tested as above.
each has minimal sequences starting with F2 and with R2. as above,
we may cancel a quarter turn from the end of stage 3 with a quarter
turn at the beginning of stage 3, to get the final figure of 56
quarter turns.

the next step is to reduce the figure for stage 3 by allowing other
turns. i only plan on allowing D, U, B2, F2, L2, R2, as in the
second stage of kociemba's algorithm. after that, i may try to reduce
the numbers for stage 2. however, in this case, i don't expect much
of a reduction (maybe 1 turn).

mike


[next] [prev] [up] [top] [help]