From cube-lovers-errors@mc.lcs.mit.edu Thu Mar 18 19:37:40 1999
Return-Path:
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 TAA14746
for ; Thu, 18 Mar 1999 19:37:39 -0500 (EST)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Message-Id: <36F18BF0.5950@hrz1.hrz.tu-darmstadt.de>
Date: Fri, 19 Mar 1999 00:27:44 +0100
From: Herbert Kociemba
Reply-To: kociemba@hrz1.hrz.tu-darmstadt.de
To: Cube Lovers
Subject: Re: Re : Re: Edges only, Ignoring Flips, Face Turn Metric
References:
Jerry Bryan wrote:
>
> On Fri, 12 Mar 1999 01:01:52 -0500 michael reid
> wrote:
>
> > i guess i'm not sure what you're doing, jerry. but i don't think
> > it should be *that* difficult. the number of configurations is
> > 12! = about 480 million. if you divide out by symmetry, you get
> > about 10 million configurations. this should be small enough to
> > store in memory and do a complete breadth-first search of the space.
> >
> When a search space consists of the elements of a cube group, it is
> easy to index the search space. But when a cube group is reduced by
> symmetry the result is generally not a group and the resultant search
> space is (in my experience) not very easy to index. The thing about
> Herbert's program that I have trouble comprehending is that he is able
> to reduce the search space by symmetry and still have the indexing be
> well behaved. He has posted a clear exposition of his method, so the
> problem is in my understanding rather than in his explanation.
I think you are right to say that the indexing of a cube group reduced
by symmetries does not behave very well. For this reason I must build a
table which maps the index to a representative of the corresponding
equivalence class. I have no method to directly compute the index.
About 10 million entries would be possible but quite a lot, so I
defined two edge permutations x and y as "equivalent" if x = MyN with
two symmetries M and N. So I reduced by another factor of about 48 and
got 208816 classes. If x is a representative of such a class with index i,
Mx with an arbitrary symmetry M is a representative of a "real" symmetry
class. The "well behaved" index of the latter is computed by 48*i +
Index(M), where index(M) enumerates the symmetries from 0 to 47.
The problem with that which I did not realize first is, that Mx and M'x
could be equivalent, which led to wrong results when computing the God's
Algorithm for positions more than 3 face turns from start (I compared my
results with Jerry's, who made a quick run for positions up to 6 face
turns). With some exta computation this problem could be fixed.
Herbert Kociemba