From cube-lovers-errors@oolong.camellia.org Mon Jul 7 02:22:55 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id CAA04972; Mon, 7 Jul 1997 02:22:54 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199707070459.AAA17039@life.ai.mit.edu>
Date: Mon, 7 Jul 1997 01:04:35 -0400
From: michael reid
To: cube-lovers@ai.mit.edu
Subject: symmetry reductions for superflip
a simple counting argument shows that some cube positions are at least
18 face turns from start, and thus the diameter of the cube group is
at least 18f. in january 1995, i showed, by exhaustive search,
that the position "superflip" is exactly 20 face turns from start.
therefore the diameter is at least 20f. this gave the first
improvement to the lower bound obtained by the counting argument.
the searching method i used at the time was my version of kociemba's
algorithm. although my symmetry reductions fit together quite well
with kociemba's algorithm, this might not be the most appropriate
searching method to use for this purpose. (i guess i could have
hacked it not to bother looking for solutions longer than 19f.
i don't remember why i didn't do this.)
my new optimal solving program can do an exhaustive search in much
less time. the symmetry reductions are similar, but much simpler.
i will try be more coherent this time with my explanation, hopefully
without being overbearing.
the first thing to note is that dik winter found a maneuver for
superflip in 20f:
F B U2 R F2 R2 B2 U' D F U2 R' L' U B2 D R2 U B2 U (20f)
therefore our concern is with searching for maneuvers of length
at most 19f.
there are three ways to transform a maneuver for superflip to get
another such maneuver, which do not change its length:
1. we may conjugate the maneuver by any symmetry of the cube.
2. we may cyclically shift the maneuver; i.e. replace
sequence_1 sequence_2 by sequence_2 sequence_1
3. we may replace the maneuver by its inverse.
(in fact, we won't use 3 here, but it might be helpful elsewhere.)
our first result is
proposition 1. any maneuver for superflip in 19f contains a 180 degree
face turn.
proof. if the proposition were false, then superflip would be an
odd number of quarter turns from start, contradiction. qed.
the relevance of this proposition is
proposition 2. suppose that a maneuver for superflip contains a 180 degree
face turn. then it can be transformed, using the above
tranformations, into a maneuver that begins with U R2.
proof. we first claim that the maneuver has two consecutive "syllables"
such that the first contains a 90 degree face turn and the second
contains a 180 degree face turn. a "syllable" is a sequence of
one or two face turns along the same axis; e.g. U D2. by
hypothesis, the maneuver has a syllable that contains a half turn.
if the claim is false, then the preceding syllable contains no
90 degree turns, and therefore consists only of half turns. but
then the syllable before that contains only half turns, by the
same reasoning. continuing in this way, we see that every syllable
consists only of half turns. therefore we have a maneuver for
superflip consisting only of half turns. this is a contradiction,
so the claim is true.
now, since the individual face turns within a syllable
commute, we may suppose that the maneuver has a 90 degree face
turn followed by a 180 degree face turn, which are along
different axes, and thus are adjacent faces. now we may
conjugate by an appropriate symmetry of the cube to suppose that
these turns are U R2. finally, we may cyclically shift the
maneuver so that these are the first two turns. qed.
proposition 3. suppose that superflip is exactly 19 face turns from
start. then applying the sequence U R2 to it brings
us 2 face turns closer to start, i.e. 17f from start.
proof. apply proposition 1 and proposition 2. qed.
we now know how to handle the case that superflip's distance from start
is exactly 19f. if the distance is less than 19f, we use the following
proposition 4. under any circumstances, applying the sequence U R2
to superflip brings us at least 1f closer to start.
proof. a minimal maneuver for superflip must contain a 90 degree twist,
and we may suppose that the next face turned is an adjacent one.
by cyclically shifting the maneuver, we may bring these two
turns to the beginning. furthermore, by symmetry, we may
suppose that the first turn is U and the second is some twist
of the R face. now by applying U to superflip, we've moved
1f closer to start, and applying R2 to this doesn't move us
any further from start, since it either combines with, or cancels
the next turn in the minimal maneuver. qed.
putting this all together, we get our desired result.
proposition 5. suppose that superflip is within 19f of start. then the
position superflip U R2 is within 17f of start.
proof. this is just combining props 3 and 4. qed.
i don't claim that these are the best reductions possible. they
suffice for our purposes.
i tested the position superflip U R2 (i.e. the position obtained by
first doing superflip, and then doing the sequence U R2) with my
optimal solver. my program took 2 hours and 40 minutes to exhaustively
search this position through 17 face turns (not including about 11
minutes to generate all the lookup tables). there were no solutions.
thus superflip is exactly 20 face turns from start. when i did the
search in january 1995, the run time was 6 days. so we see quite a bit
of improvement.
mike