From:

~~~ Subject:

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