[next] [prev] [up] Date: Sun, 08 Jan 95 03:35:54 +0100
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
[next] [prev] [up] Subject: Re: two stage filtration

i've run an exhaustive search on the coset space G / H. the number
of cosets at each distance is:

Ah, well. To think that I had the program publicly available since
February 1993 through anonymous ftp, I ought to have thought about
it when we got a machine large enough to run the program; about a
year ago. Damn ;-).

distance quarter turns face turns

I am running and will confirm tomorrow; no doubt about that.

...
 > to give a total of  2187 * 2048 * 495 = 2217093120  configurations.
 > to reduce this number somewhat, we can utilize symmetry.  there are 16
 > symmetries of the cube that preserve the  U-D axis,  and therefore
 > preserve the subgroup  H.  up to these symmetries, the number of distinct
 > corner configurations is 168, so we need only consider a mere
 > 168 * 2048 * 495 = 170311680  configurations.

(so far, this is the same approach that dik used for his calculation.)

The approach is the same, but I did avoid the embarrasment you had later.
I came up with 324 * 2048 * 495 = 328458240 configurations.

each configuration is stored with 2 bits of memory and thus the whole
space consumes about 42 megabytes. each configuration is assigned
one of 4 values:
distance is currently unknown
distance = current search depth
distance = current search depth - 1
distance < current search depth - 1
from here, i just used a simple breadth first search.

This is similar to what I did outline about that time. It comes from
a remark somebody not on this list (Arjeh Cohen) made to me about a
file helping solving the cube. You store only the distance mod 3;
that will give you a simple database to solve it. That again came
from a talk at some congress I do not remember at this time of the
night ;-).

...
 >       i) only use the 8 symmetries that preserve my choice of
 >          12 edge facelets.

I did this indeed.

run times were improved significantly by using a simple trick that i hadn't
used in earlier programs. during the first few depth levels, i use
"forward searching", i.e. i examine the neighbors of each configuration
found at the previous depth. however, after at least half the search space
has been found, i switch to "backward searching", i.e. examine the
configurations (and their neighbors) that haven't yet been found.

(have others been using this same idea when running similar search programs?)

closer analysis of this technique suggests that the switch from forward to
backward searching should occur even before half the space has been found.

Here I am a bit surprised. I would think the time needed for a phase is
entirely dependend on the number of neighbo(u)rs you have to examine. This
appears to be 6 times the number of configurations you visit. So I would
think that going the other way pays when the number of configurations not
yet decided is less than the number of configurations found in the previous
step. And no, I did not implement this; although it looks simple indeed.

Phase 2 for me needs a bit of consideration as obviously you reduced the
number of cases a bit more than I did when I wrote my program. (Mine
still does not fit in 256 Mb.)

More tomorrow.

dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn  amsterdam, nederland; e-mail: dik@cwi.nl

[next] [prev] [up] [top] [help]