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?