From BRYAN@wvnvm.wvnet.edu Mon Sep 12 17:56:28 1994
Return-Path:
Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09587; Mon, 12 Sep 94 17:56:28 EDT
Message-Id: <9409122156.AA09587@life.ai.mit.edu>
Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2)
with BSMTP id 0953; Mon, 12 Sep 94 15:35:41 EDT
Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU
(LMail V1.2a/1.8a) with BSMTP id 2448; Mon, 12 Sep 1994 15:35:41 -0400
X-Acknowledge-To:
Date: Mon, 12 Sep 1994 15:35:32 EDT
From: "Jerry Bryan"
To: "Cube Lovers List"
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
outrageous.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
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?