From:

~~~ ~~~ Subject:

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?