I want to post my God's Algorithm results for the 2x2x2 cube.
These results generally speaking replicate other results that have
been posted here as far back as ten to twelve years ago.
In order to make my numbers make sense, I need to explain how I count
the states of the 2x2x2 cube. As has been posted here several times
previously, the number is (7!)(3^6)=3,674,160. Actually, I prefer
the formulation (7!)(3^7)/3=3,674,160 because the latter formulation
clearly reflects that all the cubies can be rotated but that
rotational orientation of the last one is determined by the
rotational orientation of the others. But in any case, this
calculation is based on the following. Let any one cube be fixed
in location and rotational orientation. Then, there are
7! ways to arrange the other seven cubes, and (3^7)/3 ways to
rotate them.
But there is another way to look at it. Fix none of the cubes.
Rather, choose one to be the upper,left,front one, pick a second
one to be the upper,right,front one, etc., so that there are 8!
ways to arrange the eight cubes and (3^8)/3 ways to rotate them.
We have 8!(3^8)/3=88,179,840, which is exactly twenty-four
times larger than 3,674,160.
The reason is that the 3,674,160 figure implicitly assumes
that cubes that differ only in orientation of the overall
cube are equivalent, and there are twenty-four ways to orient
the cube in space (i.e., the order of the rotation group of
the cube is 24).
Conversely, the 88,179,840 figure implicitly assumes that
cubes that differ only in orientation of the overall cube
are distinct. They can be made equivalent by applying the
rotation group of the cube to form equivalence classes, and
there will be exactly 3,674,160 equivalence classes. Hence,
the two ways of counting are isomorphic. However, I do
prefer to characterize the "things" that the 3,674,160 figure
counts as equivalence classes, and I call 3,674,160 the
number of nodes using 24-fold symmetry.
Finally, I apply a second order-24 rotation group (I will explain
how you can have a two order-24 rotation groups on the same cube
in a follow-up post) and an order-2 reflection group. Hence, the
number of nodes to represent the entire search tree for the 2x2x2
cube should be 88,179,840/(24*24*2)=76,545, where the 76,545 figure
represents the number of equivalence classes and each equivalence
class includes 24*24*2=1152 elements. As it turns out, a few of
the equivalence classes contain fewer than 1152 elements, so that
the total number of nodes in the search tree is slightly larger
than 76,545, namely 77,802.
The tables of results below include figures both for 24-fold symmetry
and for 1152-fold symmetry. My search tree was for 1152-fold symmetry
only. I then sort of "backed in" to the results for 24-fold symmetry
by calculating the size of each equivalence class. Calculating a
search tree with 77,802 nodes representing equivalence classes, then
calculating the size of each equivalence class, was much faster than
calculating a search tree with 88,179,840 nodes or one with
3,674,160 nodes.
The little exercise with calculating the size of each equivalence
class was very gratifying in at least two respects. First, it let
me explain the disconcerting difference between 76,545 and 77,802.
Second, it let me confirm that my results were the same as everyone
else who had gone before.
>Results Using Both q-turns and h-turns
Distance Number of Number of from Nodes Nodes Start using using 24-fold 1152-fold symmetry symmetry0 1 1 1 9 2 2 54 5 3 321 19 4 1847 68 5 9992 271 6 50136 1148 7 227536 4915 8 870072 18364 9 1887748 39707 10 623800 13225 11 2644 77 ----- ------- ----- Total 3674160 77802>Results Using Only q-turns
Distance Number of Number of from Nodes Nodes Start using using 24-fold 1152-fold symmetry symmetry0 1 1 1 6 1 2 27 3 3 120 6 4 534 17 5 2256 59 6 8969 217 7 33058 738 8 114149 2465 9 360508 7646 10 930588 19641 11 1350852 28475 12 782536 16547 13 90280 1976 14 276 10 ----- ------- ----- Total 3674160 77802>Results Using Only h-turns
Distance Number of Number of from Nodes Nodes Start using using 24-fold 1152-fold symmetry symmetry0 1 1 1 3 1 2 6 1 3 11 2 4 3 2 ----- ------- ----- Total 24 7
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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?