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 1 - Forward search using a hash table. Used for distances 1 to 9.
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