# 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

## Comment viewing options

### Local Maxima

I have now completed what I hope is an accurate counting of the number of local maximum positions in the quarter-turn metric for the 3x3x3 cube considering the permutations, but not the orientations of the cubies. See the table below for the results.

The "positions" columns gives the total number of local maxima (not taking any symmetry into account). My program used symmetry in the corner cubies to reduce the effective number of positions to 984 * 12! / 2. I included the local maximum counts for this case in the "reduced" column in the table below. Finally, the "unique wrt M" column gives the number of local maxima counting only positions that are distinct with respect to the 48 symmetries of the cube. (While the "reduced" column considers symmetry of the corners, the "unique wrt M" column considers symmetry of both corners and edges.) For reference, the total positions for each case is listed at the bottom.

```Local Maxima, QTM, 3x3x3 permutations of corners and edges
(orientations ignored)

distance      positions           reduced      unique wrt M
0                   0                 0                 0
1                   0                 0                 0
2                   0                 0                 0
3                   0                 0                 0
4                   0                 0                 0
5                   0                 0                 0
6                   0                 0                 0
7                   0                 0                 0
8                   0                 0                 0
9                   0                 0                 0
10                  98                13                 7
11                 240                16                 8
12              35,380             2,027               858
13           9,630,276           248,572           201,132
14      35,533,090,748       895,464,957       740,307,100
15   1,833,521,581,740    44,697,740,880    38,198,634,121
16       3,517,318,269        83,693,410        73,289,416
17                 208                22                10
18                   1                 1                 1
-----------------    --------------    --------------
1,872,581,656,960    45,677,149,898    39,012,432,653

total positions (not just local maxima):
9,656,672,256,000   235,668,787,200   201,181,803,792
```
- Bruce Norskog

### Congratulations! I'm curio

Congratulations!

I'm curious about the unique antipode. Given that it's unique, I would think that symmetry would require that the antipode be the central inversion on both the corners and the edges. Which is to say, it must be the case that for the antipode x to be unique, it must be the case that Symm(x)=M. And when twists and flips are ignored, the identity and the central inversion are the only permutations for which Symm(x)=M.

The Pons Asinorum is an example of the central inversion of the edges, but it is only 12q from Start. The only other cases for the entire cube (when twists and flips are taken into account) where Symm(x)=M are the identity, Superflip, and the composition of Superflip with the Pons Asinorum. But when you ignore twists and flips, Superflip is 0q from Start, rather than being 24q from Start. Therefore, the corners have to be involved in an antipode that is 18q from Start.

I suppose that the unique antipode could be the permutation that is the central inversion on the corners and which fixes the edges, but the central inversion of both the corners and the edges seems more likely.

Note that when twists are taken into account, there is no permutation on the corners for which Symm(x)=M. The twists mess up the symmetry of the central inversion. But with the twists not considered, the symmetry of the central inversion on the corners really is Symm(x)=M.

### Re: Congratulations! I'm curio

> I'm curious about the unique antipode. Given that it's unique,
> I would think that symmetry would require that the antipode be
> the central inversion on both the corners and the edges. Which
> is to say, it must be the case that for the antipode x to be
> unique, it must be the case that Symm(x)=M. And when twists and
> flips are ignored, the identity and the central inversion are
> the only permutations for which Symm(x)=M.

Yes, the antipode is the permutation that is the central inversion on both the corners and the edges.

> I suppose that the unique antipode could be the permutation
> that is the central inversion on the corners and which fixes
> the edges, but the central inversion of both the corners and
> the edges seems more likely.

I also looked up the distance for the permutation that is the central inversion on the corners and which fixes the edges. It is at distance 14.

- Bruce Norskog