[next] [prev] [up] Date: Wed, 18 Jan 95 10:13:45 -0500
[next] [prev] [up] From: michael reid <mreid@ptc.com >
[next] ~~~ [up] Subject: superflip requires 20 face turns

superflip is now known to require 20 face turns. in particular, the
diameter of the cube group is at least 20 face turns (and i conjecture
that it's larger). as far as i can tell, this is the first improvement
to the lower bound (18f) given by a simple counting argument.

in my previous two messages, i gave a proof of the fact that there is a
minimal sequence for superflip in one of the following forms:

R1 F1  sequence_1  sequence_2,
R1 F2  sequence_1  sequence_2,
R1 F3  sequence_1  sequence_2,
R1 U1  sequence_1  sequence_2,
R1 U2  sequence_1  sequence_2,
R1 U3  sequence_1  sequence_2,
R1 L1  sequence_1  sequence_2,   or
R1 L3  sequence_1  sequence_2,

where sequence_2 is in the subgroup of stage 2 of kociemba's algorithm,
and sequence_1 is at most 15f long. as of monday morning, the first
six cases were completely searched, but the final two seemed to be much
slower. fortunately, there is more symmetry available here (which is at
least part of the reason that these cases are so slow).

in the case starting with R1 L1, we have four symmetries (generated by
C_R2 and C_U2) which fix the subgroup of stage 2. using these
symmetries, we may suppose that the third face turn is one of U1, U2, U3,
F1, F2 or F3.

in the case starting with R1 L3, we again have four symmetries which fix
the subgroup of stage 2. in this case, the symmetries are generated by
C_R2 and reflection through the R - L plane. using these symmetries,
we may suppose that the third face turn is one of U1, U2, F1 or F2.

even with these reductions, the last two cases are still somewhat
stubborn. finally they were completed this morning.

here's a summary of what i tested:

position tested: depth tested

superflip  R1 F1:  15f deep in stage 1
best solution found:  15 + 3 = 18f

superflip  R1 F2:  15f deep in stage 1
best solution found:  15 + 3 = 18f

superflip  R1 F3:  15f deep in stage 1
best solution found:  15 + 3 = 18f

superflip  R1 U1:  15f deep in stage 1
best solution found:  11 + 8 = 19f

superflip  R1 U2:  15f deep in stage 1
best solution found:  13 + 5 = 18f

superflip  R1 U3:  15f deep in stage 1
best solution found:  12 + 7 = 19f


superflip  R1 L1 U1:  14f deep in stage 1
best solution found:  11 + 7 = 18f

superflip  R1 L1 U2:  14f deep in stage 1
best solution found:  10 + 7 = 17f

superflip  R1 L1 U3:  14f deep in stage 1
best solution found:  11 + 7 = 18f

superflip  R1 L1 F1:  14f deep in stage 1
best solution found:  12 + 5 = 17f

superflip  R1 L1 F2:  14f deep in stage 1
best solution found:  10 + 8 = 18f

superflip  R1 L1 F3:  14f deep in stage 1
best solution found:  12 + 5 = 17f


superflip  R1 L3 U1:  14f deep in stage 1
best solution found:  14 + 3 = 17f

superflip  R1 L3 U2:  14f deep in stage 1
best solution found:  10 + 8 = 18f

superflip  R1 L3 F1:  14f deep in stage 1
best solution found:  12 + 5 = 17f

superflip  R1 L3 F2:  14f deep in stage 1
best solution found:  13 + 5 = 18f

total run time was about 210 cpu hours (somewhat more than i'd hoped for)
distributed across several machines of varying ability.

mike


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