From cube-lovers-errors@mc.lcs.mit.edu Wed Apr 29 10:54:31 1998
Return-Path:
Received: from sun28.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.1/mc) with SMTP
id KAA00312; Wed, 29 Apr 1998 10:48:07 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From cube-lovers-request@life.ai.mit.edu Wed Apr 29 00:53:36 1998
Message-Id: <3546B17A.3419@idirect.com>
Date: Wed, 29 Apr 1998 00:50:02 -0400
From: Mark Longridge
To: cube-lovers@ai.mit.edu
Cc: cubeman@idirect.com
Subject: Various Cube Thoughts
Ok, I'm back into cubing again... a few interesting, if somewhat
disjoint observations:
Summary of the 3 different types of optimal superflip sequences:
1) Superflip with minimal q turns & symmetric moves
Process has central reflection symmetry
R3 U2 B1 L3 F1 U3 B1 D1 F1 U1 D3 L1 D2 F3 R1 B3 D1 F3 U3 B3 D3 U1
(24q, 22f)
2) Superflip with minimal q turns & asymmetric moves
U1 R2 F3 R1 D3 L1 B3 R1 U3 R1 U3 D1 F3 U1 F3 U3 D3 B1 L3 F3 B3 D3 L3
(24q, 23f)
3) Superflip with minimal f turns & asymmetric moves
U1 R2 F1 B1 R1 B2 R1 U2 L1 B2 R1 U3 D3 R2 F1 D2 B2 U2 R3 L1
(28q, 20f)
------------------------------------------------------------------
No matter which cube you start searching from, e.g. pons asinorum,
12 flip, or any random cube, the dispersion of cubes is the same:
1, 12, 114, 1068, 10011... etc
So much for trying to search backwards from the 12-flip to number
the positions from (perhaps) antipode to start!
------------------------------------------------------------------
I have got Mike Reid's optimal solver to work under the dos shell
in windows 95. I finally managed to compile it using WATCOM 11.0
thusly:
wcl386 /k10000000 search.c
I had to give it a 10 megabyte stack for it to work!
It found the sequence ( F R B L )^5 to require 20 q turns, so there
is nothing better. Next I tried ( F R B L )^6 to see if that would
be 24 q but a 20 q solution was found. Mike Reid confirmed the
result on another computer running Linux.
-------------------------------------------------------------------
Lastly, some non-mathematical ideas on how to do optimal searches
of rubik's cube patterns. Using my own human solving algorithm
I solve the 4 down edge cubes last. One of the patterns I
get was solved optimally by Mike's program thusly:
D' R' D' F B' D' L' D L D F' B D R
If we assign a value of 1 to each face and add them we get:
D = 6 U = 0
F = 2 B = 2
L = 2 R = 2
Note that most of the action occurs with the D face, which I find
suggestive. After all, nothing is moved except the 4 bottom edge cubes.
Also all the other faces have an even number of turns!
My idea is perhaps with some pre-processing of a goal state it is
possible to prune the number of moves down to such a degree that
the number of moves actually tried is quite small. Also note that
this particular goal state has only 2 pairs of cubes swapped, and
all the other cubes are in place.
Now I may be using too much hindsight, but to me it is counter-
intuitive that it is possible to have 3 separate turns of the
D face! So, sequences with 3 uses of the D face should not be
considered. My theory is that ultimately with enough pre-processing
only the optimal sequences will be even considered!
-> Mark <-