[next] [prev] [up] Date: Mon, 12 Sep 94 15:35:32 -0400 (EDT)
[next] [prev] [up] From: Jerry Bryan <BRYAN@wvnvm.wvnet.edu >
~~~ ~~~ [up] Subject: God's Algorithm, Q-Moves Through Level 10
Distance   Number   Branching       Number   Branching   Ratio of
from         of      Factor           of      Factor     Cubes to
Start      Cubes                 M-Conjugate             M-Conjugate
                                    Classes               Classes

 0              1                         1
 1             12     12.000              1   1.000        12.000
 2            114      9.500              5   5.000        22.800
 3          1,068      9.368             25   5.000        42.720
 4         10,011      9.374            219   8.760        45.712
 5         93,840      9.374          1,978   9.032        47.442
 6        878,880      9.366         18,395   9.300        47.778
 7      8,221,632      9.355        171,529   9.325        47.931
 8     76,843,595      9.347      1,601,725   9.338        47.976
 9    717,789,576      9.341     14,956,266   9.338        47.993
10  6,701,836,858      9.337    139,629,194   9.336        47.997

Some of you may remember previous results where I calculated equivalence
classes of the form {m'Xmc} for all 48 elements m in M, the set of all
cube rotations and reflections, and for all 24 elements c in C, the set
of all cube rotations. This is effectively calculating M-conjugate classes
for centerless cubes. My previous data bases have contained
representative elements Y for each equivalent class {m'Xmc}. To get
cubes with centers (where rotational orientation makes a difference),
I then calculated Yc for each c in C, forming a matrix indexed by
Y and c.

The previous approach permits a very compact representation of God's
algorithm, and I used it for corners-only cubes and am presently
using it for edges-only cubes. However, I find that the {m'Xmc}
approach does not work well for whole cubes. The problem is that
the matrix is extremely sparse close to Start. With corners-only
or edges-only cube, I can calculate the entire problem. With the
whole cube, I cannot even come close to calculating the whole problem,
and the matrix representation wastes space rather than saving space.

Hence, for whole cubes, I am calculating equivalence classes (which
are M-conjugate classes) of the form {m'Xm} for all 48 elements m in M.
My data base includes a representative element Z for each M-conjugate
class {m'Xm}. This reduces the size of the problem by about 48 times,
and lets me calculate about two more levels of the search tree with the
same level of effort as before.

Just to reiterate some obvious points that have appeared before:

1) X is an arbitrary element of {m'Xm}, but Z is a particular element
of {m'Xm} chosen with a selection function.

2) Z is in {m'Xm} and we have {m'Zm} = {m'Xm}.

3) |Z| = |X| = |m'Xm| = |m'Zm| for all m in M and for all X in
{m'Xm}. This trivial equivalence is what makes M-conjugate
classes a viable approach for brute force calculation of
God's algorithm.

4) Most M-conjugate classes of the form {m'Xm} contain 48 elements.
The size of {m'Xm} can be used as a measure of the symmetry of
X, with |{m'Xm}|=1 for the most symmetric cubes and |{m'Xm}|=48
for the least symmetric cubes. Conversely, Symm(X) is the
set of all m in M such that m'Xm=X. |Symm(X)|=48 for the
most symmetric cubes, |Symm(X)|=1 for the least symmetric cubes,
and |{m'Xm}| * |Symm(X)| = 48 in all cases.

5) The ratio of cubes to M-conjugate classes is close to, but not
exactly equal to, 48. The reason the equality is inexact is
symmetry (see item #4 above). The ratio is closer to 48 when
you get further from Start because the proportion of asymmetric
cubes is higher when you are further from Start.

I actually calculated (and previously reported) God's Algorithm directly
through level 8. For levels 9 and 10, I only calculated the number of
M-equivalence classes directly. I then calculated the size of each
M-equivalence class to obtain the number of cubes. This particular data
base has 14 bytes for each cube (actually for each representative element
Z). Hence, 14*139,629,194= 1,954,808,716 bytes are required to store
level 10 (each level is in a separate file). This is about
2 gigabytes of storage, which is quite large, but which is by no means

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)              (304) 293-5192
Associate Director, WVNET                  (304) 293-5540 fax
837 Chestnut Ridge Road                     BRYAN@WVNVM
Morgantown, WV 26505                        BRYAN@WVNVM.WVNET.EDU

If you don't have time to do it right today, what makes you think you are
going to have time to do it over again tomorrow?

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