From mreid@ptc.com Wed Jan 18 10:02:03 1995 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20530; Wed, 18 Jan 95 10:02:03 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA06914; Wed, 18 Jan 95 10:00:38 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA00811; Wed, 18 Jan 1995 10:13:45 -0500 Date: Wed, 18 Jan 1995 10:13:45 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9501181513.AA00811@ducie.ptc.com> To: cube-lovers@ai.mit.edu Subject: superflip requires 20 face turns Content-Length: 3124 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