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