From cube-lovers-errors@mc.lcs.mit.edu  Mon Dec 21 14:00:52 1998
Return-Path: <cube-lovers-errors@mc.lcs.mit.edu>
Received: from sun28.aic.nrl.navy.mil (sun28.aic.nrl.navy.mil [132.250.84.38])
	by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id OAA01463
	for <cube-lovers-outbound@mc.lcs.mit.edu>; Mon, 21 Dec 1998 14:00:52 -0500 (EST)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Message-Id: <367BDD1D.DE6@hrz1.hrz.tu-darmstadt.de>
Date: Sat, 19 Dec 1998 18:06:37 +0100
From: Herbert Kociemba <kociemba@hrz1.hrz.tu-darmstadt.de>
Reply-To: kociemba@hrz1.hrz.tu-darmstadt.de
To: cube-lovers@ai.mit.edu
Cc: michael reid <reid@math.brown.edu>
Subject: Re: Optimal Cube Solver
References: <199812180306.WAA21451@cauchy.math.brown.edu>

michael reid wrote:

> herbert, you might be interested in what my sub-optimal program
> (the one based on your two-stage algorithm) does about edge
> permutations.  i have this extra coordinate i call "sliceedge",
> (really this is just another coset space) which considers the
> locations of four distinguishable edges.  there are 12*11*10*9 = 11880
> possibilities for this coordinate.  when the cube is entered, it
> calculates the corresponding coordinate for edges in the U-D slice,
> also for edges in the F-B slice, and also for the R-L slice.
> then i have lookup tables to tell me how this coordinate transforms
> under turns.  this lookup table is 18 * 11880 shorts = 427680 bytes.
>
> when stage 2 is reached, i have a lookup table that maps this
> coordinate into permutations of the four U-D slice edges.  actually,
> only 24 of the entries are valid, but only these occur, since we've
> reached stage 2.  this lookup table is 11880 chars.

I already made some experience with the "sliceedge"-coordinate before. I
built it in the way:
24*position of the 4 edges + permutation of the 4 edges,
where the position range is from 0 to 494 and permutation ranges from 0
to 23.
In this way when reaching stage 2, the "sliceedge"-coordinate
automatically is in the range from 0 to 23 and you need no lookup table
at all.

> there's also a lookup table to transform the "sliceedge" coordinate
> into another coordinate, which gives the locations of four
> distinguishable edges among the eight U and D edges.  this coordinate
> has 8*7*6*5 = 1680 possibilities, and the lookup table is 11880 shorts.
>
> the big lookup table is the one that takes two of these last coordinates
> and transforms it into a permutation of the eight U and D edges.
> this table has 1680 * 1680 shorts = about 5.5 megabytes.  most of
> the entries are garbage, only 40320 = 8! actually occur, since we've
> reached stage 2.

This seems an interesting approach. Using the
edge-permutation-coordinate in the way I described it before, I need
about 20MB for the lookup-table which tells the coordinate-tranformation
under turns, which is quite a lot. Maybe I also try your method.

Herbert