From cube-lovers-errors@oolong.camellia.org  Fri Jun  6 11:48:24 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 LAA10757; Fri, 6 Jun 1997 11:48:23 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Fri, 6 Jun 1997 09:36:32 -0400 (EDT)
Message-Id: <199706061336.JAA05762@spork.bbn.com>
From: Allan Wechsler <awechsle@bbn.com>
To: SCHMIDTG@iccgcc.cle.ab.com
Cc: cube-lovers@ai.mit.edu
Subject: Categorization of cube solving programs
In-Reply-To: <970605225656.21412b24@iccgcc.cle.ab.com>
References: <970605225656.21412b24@iccgcc.cle.ab.com>

    [SCHMIDTG@iccgcc.cle.ab.com:]
    Class 4:	A program which attempts to discover an ALGORITHM to
    		solve ALL randomized cubes.  The program starts off only
    		with a model of the cube and attempts to discover a general
    		procedure which solves all permutations of the cube.

There's a classic procedure, the Furst-Hopcroft-Luks algorithm, that
can solve any permutation puzzle in polynomial time.  Here's a
citation I snarfed from the web.

Merrick Furst, John Hopcroft, and Eugene Luks. Polynomial-time 
    algorithms for permutation groups. In 21st Annual Symposium 
    on Foundations of Computer Science, pages 36-41, Syracuse, 
    New York, 13-15 October 1980. IEEE.

The solutions it finds are typically very long -- for the cube, it's
typically thousands of moves.  But that's really not too shabby -- the
first solution _I_ found was thousands of moves long too.

The algorithm is extremely mechanical.  It involves building a library
of tools that leave more and more of the pieces fixed, permuting fewer
and fewer of them.

-A