   Date: Sat, 04 Dec 93 21:04:23 -0500 (EST)   From: Jerry Bryan <BRYAN%WVNVM.BITNET@mitvma.mit.edu >
~~~ ~~~ Subject: God's Algorithm for the 2x2x2 Pocket Cube

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

>Results Using Both q-turns and h-turns

```Distance           Number of          Number of
from               Nodes              Nodes
Start              using              using
24-fold            1152-fold
symmetry           symmetry
```
```    0                       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           symmetry
```
```    0                       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           symmetry
```
```    0                       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     