From cube-lovers-errors@oolong.camellia.org Sun Jun 1 21:39:51 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 VAA01513; Sun, 1 Jun 1997 21:39:51 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 01 Jun 1997 21:06:18 -0400 (EDT)
From: Jerry Bryan
Subject: Re: Description of algorithm for finding minimal-move solutions to
Rubik's Cube
In-reply-to: <199705300024.RAA18247@denali.cs.ucla.edu>
To: Richard E Korf
Cc: Cube-Lovers@ai.mit.edu
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
On Thu, 29 May 1997, Richard E Korf wrote:
> For example, if we consider just the corner cubies, there are only about 88
> million possible states they could be in (8!x3^7). We exhaustively build and
> store a table, using breadth-first search, that tells us the minimum number of
> moves needed to solve just the corner cubies from every possible combination,
> ignoring the edge cubies. This value ranges from 0 to 11 moves, averages 8.764
> moves, and requires only 4 bits per state. (We could reduce this further using
> an idea of Dan Hoey's published in this list awhile ago.) This table only has
> to be computed once, taking about a half hour, and requires about 42 megabytes
> of memory to store (a megabyte is 1048576 bytes).
I have an old program, developed on a 286 PC with a 10MB harddisk, which
stores the entire solution for the corners in about 2.5MB. Details are in
the archives, but it uses representatives of the form Repr{m'Xmc}. The
representatives consitute the solution of the 2x2x2 and take about .625MB.
The remaining storage is in a format I call Repr{m'Xmc}*C to take care of
the corners of the 3x3x3. However, I would guess that even though this
format would save a great deal of memory, it would also very much slow
your program down, rather than speeding it up, because of the rather
arcane indexing required.
This brings up a point which I think has been taken for granted in the
archives but which I think has never been spelled out in detail. In its
most simple-minded form, a search involves storing both permutations and
distances from Start. But sometimes you can get by with storing only the
permutations, and sometimes you can get by with storing only the
distances.
In this case, you are storing the entire corner group, and therefore you
can get by with storing only the distances. That is, you have obviously
developed an easy-to-calculate function and an inverse to map between the
corner permutations and an index set, say 1..|GC| or maybe 0..|GC-1|.
Hence, you don't need to store the permutations themselves. My
Repr{m'Xmc} technique stores only a subset of the permutations. There is
a one-to-one correspondence between the subset which is stored and an
index set, but it is not very easy to calculate (actually, it involves
some binary searching).
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990