From cube-lovers-errors@oolong.camellia.org Thu Jul 10 00:56:16 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 AAA12818; Thu, 10 Jul 1997 00:56:16 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-Id: <199707100450.AAA14097@life.ai.mit.edu>
Date: Thu, 10 Jul 1997 00:54:58 -0400
From: michael reid
To: cube-lovers@ai.mit.edu
Subject: all minimal maneuvers for superflip (face turn metric)
i can now give all minimal maneuvers for superflip in the face turn
metric. recall that there are three operations we may apply to any
maneuver for superflip which give another maneuver of the same 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.
my original search (january 1995) for superflip in 19 face turns was
divided into 16 cases. since i used my (unhacked) version of kociemba's
algorithm, the search through each case produced maneuvers for superflip,
and 8 of these cases found maneuvers of length 20f. i previously reported
that these were each equivalent to dik winter's maneuver, using the three
operations above. however, i was mistaken about this; there were two
different maneuvers which differ only very slightly.
to facilitate an exhaustive search through 20f, i'll use a result of a
previous search.
proposition. any maneuver for superflip in 20f contains a 180 degree
face turn.
proof. otherwise the maneuver would be 20 quarter turns long. however, i
did an exhaustive search through 20q and found no maneuvers. qed.
(in fact, this quarter turn result was later improved by jerry bryan, who
showed that superflip is not within 22q of start, and therefore is exactly
24q from start.)
now the symmetry reductions show that we may take the first two face turns
to be U R2 . my program exhaustively searched the position superflip U R2
through 18f. it took 35 hours, and found 30 maneuvers, which came in two
different types:
U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 (20f)
U R2 F B R B2 R U2 L B2 R U' D' R2 F D2 B2 U2 R' L (20f)
note that these are the same except for the last 5 face turns. (this gives
the relation R' L B2 U2 F2 R L' U2 B2 D2 = identity; alternatively, the
same sequence produces (f++)(d++) in the supergroup.)
from this, we can count the exact number of 20f sequences for superflip.
both of the above may be cyclically shifted in 23 different ways. we get
23 different ways, instead of 20, because there are three separate pairs
of consecutive twists of opposite faces. we'd consider
sequence_1 U D sequence_2 and sequence_1 D U sequence_2
to be the same, but we wouldn't consider
U sequence D and D sequence U
to be the same. yet cyclic shifting of these last two produces the same
maneuver.
we can also conjugate by any of the 48 symmetries of the cube, and we can
also invert any of the maneuvers. all these operations produce different
maneuvers, so we get a total of 2 * 23 * 48 * 2 = 4416 different maneuvers.
by counting, the number of different sequences of length <= 19f is about
82 times as many positions the cube has. thus a position has, on average,
82 maneuvers of length <= 19f, although superflip has 0. the number of
different sequences of length 20f is about 1016 times the number of
positions, so a position has, on average, 1016 different maneuvers of
length 20f. superflip has more than 4 times that many.
here are the 30 solutions my program found for superflip U R2. hopefully
i haven't made any mistakes this time. they should all be equivalent to
one of the two listed above.
U R2 F U2 F2 D2 R' L U R2 F' B' R D2 L F2 R D2 R D (20f)
U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 (20f)
U R2 F B R B2 R U2 L B2 R U' D' R2 F D2 B2 U2 R' L (20f)
U R2 F R' L F2 D2 B2 U R2 F' B' R D2 L F2 R D2 R D (20f)
U R2 F2 L2 F D2 R L D R2 D F2 U R2 D F' B' D2 L D' (20f)
U R2 F2 L2 F' U2 R' L' U' R2 U' F2 D' R2 U' F B U2 L' D' (20f)
U R2 F2 L2 B D2 R' L' D F2 U R2 D F2 D F B D2 R D' (20f)
U R2 F2 L2 B' U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' D' (20f)
U R2 F' U2 B2 D2 R L' D' R2 F' B' R' B2 R' D2 L' B2 R' D (20f)
U R2 F' B' R D2 L F2 R D2 R U D R2 F U2 F2 D2 R' L (20f)
U R2 F' B' R D2 L F2 R D2 R U D R2 F R' L F2 D2 B2 (20f)
U R2 F' R L' B2 D2 F2 D' R2 F' B' R' B2 R' D2 L' B2 R' D (20f)
U R2 U B2 D R2 U F' B' U2 L F2 R2 B2 U' D B U2 R L (20f)
U R2 U B2 D R2 U F' B' U2 L U' D R2 B2 L2 B U2 R L (20f)
U R2 U R L U2 F L2 F2 R2 U' D L U2 F' B' U R2 D F2 (20f)
U R2 U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 (20f)
U R2 U2 L2 F' B R F2 U' D' F L2 B U2 F L2 F R L F2 (20f)
U R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R U2 R D (20f)
U R2 B D2 B2 U2 R' L D R2 F' B' R U2 L B2 R U2 R D (20f)
U R2 B' R L' F2 U2 B2 U' R2 F' B' R' F2 R' U2 L' F2 R' D (20f)
U R2 B' D2 F2 U2 R L' U' R2 F' B' R' F2 R' U2 L' F2 R' D (20f)
U R2 D F2 U R2 U R L U2 F L2 F2 R2 U' D L U2 F' B' (20f)
U R2 D F2 U R2 U R L U2 F U' D F2 R2 B2 L U2 F' B' (20f)
U R2 D F2 U R' L' U2 B L2 F2 R2 U' D R U2 F B U F2 (20f)
U R2 D F2 U R' L' U2 B U' D F2 R2 B2 R U2 F B U F2 (20f)
U R2 D F2 D F B D2 R U D' R2 F2 L2 B D2 R' L' D F2 (20f)
U R2 D F2 D F B D2 R B2 R2 F2 U D' B D2 R' L' D F2 (20f)
U R2 D F' B' D2 L U D' R2 F2 L2 F D2 R L D R2 D F2 (20f)
U R2 D F' B' D2 L B2 R2 F2 U D' F D2 R L D R2 D F2 (20f)
U R2 D2 L2 F B' L B2 U D B D2 B L2 F D2 B R' L' B2 (20f)
mike