From cube-lovers-errors@oolong.camellia.org Thu Jun 5 22:58:32 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 WAA09163; Thu, 5 Jun 1997 22:58:32 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org From: SCHMIDTG@iccgcc.cle.ab.com Date: Thu, 5 Jun 1997 22:56:56 -0400 (EDT) To: cube-lovers@ai.mit.edu Message-Id: <970605225656.21412b24@iccgcc.cle.ab.com> Subject: Categorization of cube solving programs Cube Lovers, Since I'm interested in such things, I came up with the following categories of cube solving programs in general order of increasing sophistication: Class 1: Simply provide a simulation of the cube and allow the user to manipulate the cube model via some cube operator notation (e.g. Singmaster). May also allow the user to save/restore/replay lists of moves and possibly to build up sequences of "macro operators". Might allow the user to input a given cube state. Might also allow the user to 'solve' the cube by replaying all user made moves in reverse. Often these programs have very nice 3D graphics. Class 2: A program which solves the cube by implementing a canned algorithm (or 'book procedure'). Basically, a straight forward implementation of a known cube solving process. These programs generally work through a series of stages to solve the cube and do not generally produce optimal solutions. Class 3: A program that when given a specific instance of the cube, attempts to 'discover' or learn a sequence which will solve that particular instance. That sequence is not usually considered general purpose since it will only apply to solving from the given position. It may be possible to find a minimal sequence tailored to the given position. The Kociemba and the recent Korf program fall into this category. These programs are capable of discovering optimal or near optimal solutions to a given cube instance. 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. Korf wrote a program to do this in the mid 1980s. The program was able to learn a complete set of sequences (a.k.a. 'macros') sufficient to solve any scrambled cube. The resulting algorithm is very much like a Class 2 algorithm as it works in stages to solve the cube and does not generally produce optimal solutions. I believe Korf's program is the only program ever achieved that can be placed in this category. Needless to say, I find Class 3 and Class 4 cube programs the most interesting. Someday, I would like to develop a Class 4 program of my own that works on principles that differ from the Korf program. -- Greg