From cube-lovers-errors@oolong.camellia.org Wed Jun 11 16:11: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 QAA14364; Wed, 11 Jun 1997 16:11:24 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Message-ID: <339EF3BF.766D@hrz1.hrz.th-darmstadt.de> Date: Wed, 11 Jun 1997 20:51:44 +0200 From: Herbert Kociemba X-Mailer: Mozilla 3.0 (Win95; I) MIME-Version: 1.0 To: cube-lovers@ai.mit.edu Subject: Re: Detailed explanation of two phase algorithm References: <970611003555.21417ec3@iccgcc.cle.ab.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit SCHMIDTG@iccgcc.cle.ab.com wrote: > I do have one last question regarding the pruning tables. While > the three tables used in phase1 are clear, I do not recall reading > a description of the tables that are used in phase2. In phase2, the state of the cube also is described by a triple (x,y,z), in this case 0<=x<8! describes a permutation of the 8 corners, 0<=y<8! describes a permutation of the 8 UD-slice edges and 0<=z<4! describes a permutation of the middleslice edges. Because the overall permutation must be even, only half of the triples belong to physical cubes. We could correct this, by defining the z coordinate to describe one of the 12 possibilities for the locations of two middleslice edges - the other two edges will then be corrected automatic. But there are good reasons not to do so (which I think is not necessary to explain here). > I have also been studying his code to try to understand how he generates > these tables. He does not seem to be using breadth-first-search to > fill in these tables as Korf does. > I only use the "mixed" tables. How to generate the tables is quite obvious and though I don't know how Dik does it I'm sure it is similar: 1. On initialisation set all elements of the table to 0xf (we use four bits per entry), only the element belonging to (x0,y0,z0) is set to 0. Set L=0, n_done=1, n_old=1 (n_done denotes the number of valid tableentries). 2. Check all elements of the table one after the other. If an entry is 0xf, do nothing. If the entry is L, compute the the 18 possible "child nodes" and check, if the corresponding tableentry is 0xf. Only in this case set it to L+1 and increment n_done. 3. Check if n_done=n_old. In this case we are ready. Else increment L, set n_old=n_done and goto 2. > I will be interested in looking at your new program when it becomes > available. I'm writing too much to this mailing list and do not work at my windows-help! The program itself is ready. I did a two hours run on each of Rich Korfs 10 random cubes on a Pentium133 with 16MB RAM and the result were really pleasing: The generated maneuver lenghts were on the average less than 1 move away from Rich Korfs optimal solutions (exactly: 9 moves more for the 10 cubes). Best regards, Herbert