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 <-