From cube-lovers-errors@oolong.camellia.org Fri May 30 20:33:43 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 UAA23656; Fri, 30 May 1997 20:33:43 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <338F7124.73A6@hrz1.hrz.th-darmstadt.de>
Date: Sat, 31 May 1997 02:30:28 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Re: Description of algorithm for finding minimal-move solutions to Rubik's Cube
References: <199705300024.RAA18247@denali.cs.ucla.edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Richard E Korf wrote:
>
> Dear Cube-Lovers,
> Here is the promised short description of my algorithm for finding optimal
> solutions to Rubik's Cube.
>From the description it is evident, that the algorithm Richard E Korf
uses is basically identical to the the sub-algorithm which is used in
each stage of my two stage algorithm to solve the cube. What he calls
"heuristic functions" are the "pruning tables" of Dik Winter and Michal
Reid and the "filters" in the original description of the algorithm in
CFF 28 (April 1992) of the Dutch Cubist Club. Here is a short summary of
this algorithm in the version I implemented in a windows95 program
requiring 16Mbyte of Ram. When I will have included a help-function
within the next weeks, I will offer it to all interested cubists for
free:
In phase 1, the cube is transformed to an element of the subgroup
generated by __. This is equivalent to restore the
orientation of the 8 corners and 12 edges and to put the 4 edges of the
UD-slice in that slice. There are 3^7=2187 possible states for the
corner orientations, 2^11=2048 possible edge orientations and
12*11*10*9/(1*2*3*4)=495 possible positions for the 4 edges of the
UD-slice. The "heuristic functions" consist of three tables, using 4
bits for each entry. The first table stores the minimum numbers to solve
the 2187*2048 possible states to restore the orientation of both edges
and corners, the other tables have 2187*495 and 2048*495 entries and
store the corresponding minimum numbers.
Dik Winter proved, that 12 moves always suffice to get to this subgroup.
In phase 2, the cube is solved in this subgroup, using only
U,D,R2,L2,F2, and B2. Now we have do restore the permutations of the
corners, edges and middle slice. There are 8! states for the corner
permutations, 8! states for the edge permutations and 4! states for the
permutations of the UD-slice. The "heuristic functions" consist of only
two tables, storing the minimum numbers to restore both edges and
UD-Slice and both corners and UD-Slice, having 8!*4! entries each.
The table for the minimum numbers to restore both edges and corners
would have 8!*8! entries and is not possible with the current hardware.
Michael Reid proved, that 18 moves always suffice in this subgroup.
Having found a solution in stage1 and stage2 the algorithm does not
stop, but generates other solutions in stage1. So if for example we have
10 moves in stage1 and 12 moves in stage2, there might be a solution
with 11 moves in stage1 but only 10 moves in stage2. Running long
enough, the algorithm will find the overall optimal solution, having no
moves in stage2 then.
Due to the smaller size of the subgroups a first solution usually will
be
found within seconds. This first solution is optimal for phase1, but
indeed (usually) not optimal for the overall solution. Typically you
will have solutions with less then 20 moves within minutes and the
optimal solution for states with lets say less then 16 moves will be
found within a reaseonable time.
Herbert
__