From cube-lovers-errors@oolong.camellia.org Tue Jul 8 00:16:07 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 AAA07853; Tue, 8 Jul 1997 00:16:06 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199707080413.AAA00423@life.ai.mit.edu>
Date: Tue, 8 Jul 1997 00:18:18 -0400
From: michael reid
To: cube-lovers@ai.mit.edu
Subject: superfliptwist requires 20 face turns
i can now show that the pattern "superfliptwist" is exactly 20 face
turns from start. this position was proposed as a likely antipode
of start by cubologist christoph bandelow. in the german edition
of his book "einfuerung in die cubologie" he offered a prize for the
shortest maneuver for this pattern. the prize was collected by rainer
aus dem spring, who found a maneuver in 22 face turns. much later,
a maneuver of length 20f was found by herbert kociemba:
D F2 U' B2 R2 B2 R2 L B' D' F D2 F B2 U F' L R U2 F' (20f)
as one of the first applications of his ingenious searching algorithm.
i'll try not to be so verbose with my symmetry reductions this time.
first note that "superfliptwist" does not describe a unique position
of the cube; there are two possible orientations. in this context,
i use the term "position" to refer to one of the 43252003274489856000
possible configurations, and the term "pattern" to refer to an
equivalence class of positions under symmetries of the cube.
(this concept has been discussed by dan hoey and jerry bryan as
the "real size of cube space" i.e. the number of patterns.)
the following two facts are easily verified:
* superfliptwist commutes with the square of each face turn.
* it does not commute with 90 degree slices (e.g. U D') or 90 degree
antislices (e.g. U D), however, if A is a 90 degree slice or
antislice, then
A superfliptwist A^(-1)
is also superfliptwist, but in the other orientation.
these facts lead to the importance of the following
proposition. superfliptwist is not in the subgroup generated by slices
and antislices. (note that this group contains all squares
of face turns.)
proof. we may ignore the corners and just show that all edges cannot be
flipped in this subgroup. to do this, we choose dominant facelets
on the 12 edges as follows: choose the U or D facelet of the edges
in the R-L slice, the R or L facelet of the edges in the F-B slice
and the F or B facelet of the edges in the U-D slice. now we may
define the flip of an edge that is not in its correct location.
all edges start in the correct orientation. a 90 degree slice or
antislice along the U-D axis changes the orientation of all eight
edges in the F-B slices and R-L slices. similarly, a 90 degree
slice or antislice along the F-B or R-L axis flips all edges in
two different slices. within this subgroup, either all edges in
a given slice are flipped, or none are flipped, and furthermore,
the number of the three slices with flipped edges is even, i.e.
0 or 2. however, superfliptwist has all three slices with
flipped edges, so it is not in this subgroup. qed.
now consider the first syllable of a minimal maneuver for superfliptwist.
("syllable" was defined in my previous message.) if this is a single
180 degree turn, then we may cyclically shift this to the end of the
maneuver. similarly, a slice squared may also be shifted to the end
of the maneuver. furthermore, 90 degree slices and or antislices may
also be shifted to the end of the maneuver, with only the mild effect
of changing which orientation of superfliptwist we're doing. from the
proposition, we eventually find a syllable which is not of these types,
and is therefore of type U or D2 U. in the case of D2 U , we may
shift the D2 to the back of the maneuver, so we may suppose that the
first face turn is U . furthermore, by conjugating by the cube rotation
C_U, if necessary, we may suppose that our maneuver solves our preferred
orientation of superflip. the second face turn is in a different syllable,
so it is an adjacent face. conjugating by C_U2, if necessary, brings this
face to either R or F. therefore we may suppose that the first two
face turns are one of the six sequences
U R , U R2 , U R', U F , U F2 or U F' .
to show that superfliptwist is not within 19f of start, i tested the
six patterns obtained by applying these sequences to it. it took my
program 7.5 hours to exhaustively search all of these through 17f.
(these positions ran a bit faster than most of the others i've tested.
this is partly because superfliptwist is 15 face turns from my "target"
subgroup, so larger parts of the search tree are pruned.) no solutions
were found, so superfliptwist requires 20 face turns.
i also let the first situation run partially through depth 18f. in about
4 and a half hours, it found a solution which yields
U R F' B U' D' F U' D F L F' L' U R D F U R L (20f, 20q)
this is automatically minimal in the quarter turn metric!
mike