An analysis of the corner and edge permutations of the 3x3x3 cube

I have generated a distance table using the quarter-turn metric for positions of the Rubik's cube (the standard 3x3x3 cube) where the orientation of the cubies is ignored. That is, the permutation of the corner cubies and the permutation of the edge cubies are considered, but not the orientation of either the edge or corner cubies. This is a set of 8!*12!/2 or 9,656,672,256,000 positions. To the best of my knowledge, this is (now) the largest "subset" of the 3x3x3 cube that this has been done for!

I used symmetry in the corner permutations, so that my programs "only" needed to store values for 984*12!/2 or 235,668,787,200 positions. The "real" size (considering symmetry in both the corner permutations and edge permutations) I found to be 201,181,803,792 positions. So about 17% of the stored positions are redundant with respect to the set of symmetrically distinct positions.

984 disk files were used to store the distances. That's one file for each corner permutation that is unique with respect to the symmetries of the cube. Four bits were used to store each distance, allowing packing two values into a byte. This is possible since (when the quarter-turn metric is used) the least significant bit (LSB) of the distance is always determined by the "even-ness" or "odd-ness" of the corner permutation. So the LSB of the distance values was not stored in the files. Each file contains 12!/4 (119,750,400) bytes. (12! is the total number of edge permutations. This is divided by 4, since only half of the edge permutations match the parity of the corner permutation, and each byte contains two values.) Transferring the 984 files onto single-layer DVD data discs (capacity 4.7*10^9 bytes) requires 26 discs (without data compression, anyway).

Since the number of positions was much too large to store information for all of them in memory at the same time, the 235,668,787,200 positions were subdivided according to the corner permutation. So there are 984 of these subdivisions with each containing 12!/2 edge permutations.

Suppose we have found all the positions of distance d-1 and are now looking for the positions of distance d. Since (in the quarter-turn metric) all the positions of distance d will have a corner permutation that is either even parity or odd parity, depending on whether d is even or odd, only half of these subdivisions contain candidates for the "new" positions to be found. (I will refer to this set of subdivisions as the "search space" for the current iteration, associated with distance d.) If the processing of the search space is restricted to one of these subdivisions at a time, at most 12 subdivisions (from the set of 492 with the opposite corner parity) will contain positions that can be reached with one quarter turn. It is not necessary to limit the processing to do only one of the subdivisions at a time, if available memory permits. Hence, the overall problem could be broken down into reasonable size pieces that could be done separately.

The processing was done in three stages.

Stage 2 - Forward search with the search space divided into 41 sets of 12*12!/2 positions each. Used for distances 10 to 13.

Stage 3 - Backward search with the search space divided into 492 sets of 12!/2 positions each. Used for distances 14 and up.

Below is a basic summary of the results. The "reduced count" column gives the number of positions according to the way that my programs kept track of them, taking corner symmetry into account, but not edge symmetry. I include it in case it is of interest to anyone. The "unique wrt M" column is probably of more interest as it gives the actual number of positions with respect to the symmetries of the cube. (It is conventional to refer to the group of symmetries of the cube as M when using group theory to analyze Rubik's cube.)

Distance       Positions    "Reduced count"      Unique wrt M
--------       ---------    ---------------      ------------
 0q                    1                  1                 1
 1q                   12                  1                 1
 2q                  114                  5                 5
 3q                1,068                 31                25
 4q               10,011                268               219
 5q               93,840              2,330             1,978
 6q              877,956             23,404            18,379
 7q            8,197,896            201,602           171,028
 8q           76,405,543          1,951,875         1,592,595
 9q          710,142,108         17,435,880        14,796,823
10q        6,565,779,580        164,101,507       136,794,318
11q       59,762,006,092      1,462,835,792     1,245,063,309
12q      506,821,901,799     12,506,730,080    10,558,868,042
13q    2,893,096,350,672     70,651,659,130    60,273,098,704
14q    4,311,353,832,128    105,077,892,969    89,820,338,857
15q    1,874,759,336,092     45,702,258,811    39,057,770,017
16q        3,517,320,867         83,693,490        73,289,479
17q                  220                 23                11
18q                    1                  1                 1
       -----------------    ---------------   ---------------
       9,656,672,256,000    235,668,787,200   201,181,803,792

A 2.4GHz Pentium 4 with 1GB of RAM was used. A little more than a month elapsed from when the first data files were written until the final files were generated. The total run-time was somewhere around 375 hours.

- Bruce Norskog