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