Refining Bruce Norskog's 4x4x4 five stage analysis

Bruce Norskog designed a five stage procedure to solve 4x4x4 positions, where the last stage is solving inside the squares subgroup. When I rewrote the code in Java to be used for the official WCA scrambler program, I found a few improvements on coordinate representation and symmetry reduction that I think is worth sharing.

Except for the last stage where centers need to be solved, every other stage needs to place 8 centers from a single axis (RL, FB or UD centers) in their correct faces (RL, FB or UD faces), in one of the 12 positions that can then be solved using only half turns. However, as pointed by Shuang Chen in his analysis, we don't need to store the exact colours of centers but only if two centers have the same or different colours. This reduces the number of center coordinates by 2.

Also, as opposed to the 3x3x3, 4x4x4 does not have fixed centers, which allows us to do more symmetry reduction. I'm representing a sym-coordinate as:
s1 * g * < H > * s1' * s2'
where g * < H > is a coset, s1 and s2 are symmetries from subgroups S1 and S2 of the group M of symmetries of the cube. s1 is the usual conjugated symmetry, and s2 correspond to a rotation of the cube, which is possible on the 4x4x4. Using carefully chosen subgroups S1 and S2 for each stage, more symmetry reduction is achieved. I will be using the Schoenflies symbols for subgroups of M in the following.

Stage 1

The goal is to orient the corner cubies and put the u- and d-layer edges into those two layers. (A d-layer edge may be in u layer, and a u-layer edge may be in the d layer.)

Turns allowed:

    U, U', U2, u, u', u2, D, D', D2, d, d', d2,
    L, L', L2, l, l', l2, R, R', R2, r, r', r2,
    F, F', F2, f, f', f2, B, B', B2, b, b', b2

There are 3 possibilities for each corner orientation and 8 corners so 3^8 possibilities. However, when setting the orientation of 7 corners, the 8th is fixed so only 3^7 = 2,187 cases.

For the edges, we have to record the position of 8 edges among 24 slots, so C^24_8 = 735,471 cases. This coordinate is reduced by symmetry. There are 48 symmetries in this group. However, if we apply standard conjugacy symmetry, we will achieve only a 16 factor reduction. There are in fact three sets of solved positions for edges: u- and d-layer edges can be placed either in u/d layers, in f/b layers or r/l layers. The cube has then to be rotated by a 120-degree turns about the UFL-DBR axis to put the u- and d-layer edges in u/d layers. To take into account these three sets of solved states, we add the rotation along the UFL-DBR axis in the symmetry reduction, which gives, using the notation above, S1 = M and S2 = C3 (generated by a 120-degree turn along the UFL-DBR axis). It gives 15,582 sym-coordinates for edges.

The overall space of this stage is 2,187 * 15,582 = 34,077,834.

                    Slice turns
              ------------------------
    distance  positions         unique
    --------  ---------         ------
       0              3              1
       1              6              1
       2            144              4
       3          2,796             66
       4         48,324          1,033
       5        745,302         15,620
       6     10,030,470        209,273
       7    103,416,912      2,155,397
       8    575,138,592     11,984,424
       9    826,559,202     17,222,730
      10     92,489,544      1,927,399
      11         43,782            916
          -------------    -----------
          1,608,475,077     33,516,864

Stage 2

The goal is to put front and back centers onto the front and back faces into one of the twelve configurations that can be solved using only half-turn moves, and arrange u- and d-layer edges within the u- and d-layers so that they will be in one of the 96 configurations that can be solved using only half-turn moves.

Turns allowed:

    U, U', U2, u, u', u2, D, D', D2, d, d', d2,
           L2, l, l', l2,        R2, r, r', r2,
           F2, f, f', f2,        B2, b, b', b2

As for edges of stage 1, there are C^24_8 = 735,471 cases for storing the position of the 8 F/B centers, and we also need to keep track of which centers are F and which are B, requiring another C^8_4 = 70, so a total of 735,471 * 70 = 51,482,970. However, we don't need to track the exact colour of those centers, but only if two centers are from the same or different colours. This reduces by a factor of two, giving 735,471 * 35 = 25,741,485. This (large) coordinate is reduced by symmetry (16 symmetries). As in stage 1, if we apply conjugated symmetries only, we get a effective reduction factor of 8. Centers can be solved on F/B faces, but also on R/L faces, followed by a 90-degree rotation along the UD axis. We incorporated this rotation in our symmetry reduction, giving S1 = D4h (all symmetries that preserve the UD axis) and S2 = C4 (generated by a 90-degree rotation along the UD axis). This gives 1,612,515 unique coordinates for centers.

For the edges, the total number of permutations is 8! = 40,320 and there are 96 configurations that are considered solved (square group), so the coordinate is 40,320/96 = 420.

The overall space of this stage is 1,612,515 * 420 = 677,256,300

                    Slice turns
              ------------------------
    distance  positions         unique
    --------  ---------         ------
       0             12              6
       1             36              8
       2            684             54
       3          9,254            661
       4        103,998          6,785
       5      1,149,674         73,297
       6     11,929,486        750,382
       7     92,729,838      5,803,099
       8    447,778,202     27,991,967
       9  1,247,722,776     77,990,037
      10  1,930,825,644    120,695,743
      11  2,215,400,576    138,498,874
      12  2,607,462,418    163,000,022
      13  1,828,141,454    114,282,664
      14    426,682,056     26,675,281
      15      1,487,536         93,585
      16             56              5
           ------------  -------------
         10,811,423,700    675,862,470

Stage 3

The goal is to put centers for left and right faces into the left and right faces so that they are in one of the 12 configurations that can be solved using only half-turn moves, and put top and bottom layer edges into positions such that the U or D facelet is facing either up or down. Also, put these edges into an even permutation.

Turns allowed:

    U, U', U2,        u2, D, D', D2,        d2,
           L2,        l2,        R2,        r2,
           F2, f, f', f2,        B2, b, b', b2

For centers, this is the same as for stage 2, except that now there are only 16 remaining slots for one center, as F and B faces are filled during stage 2. Using the same principle, the center coordinate is C^16_8 * C^8_4 = 12,870 * 35 = 450,450. Using symmetry reduction (8 in this stage), we only need to store 56,980 positions. There is no gain to use cube rotations here, so we have S1 = D2h (face) (all symmetries that don't swap axes) and S2 = C1 ({id}).

For edges, we need to put half of the edges in half of the positions, so C^16_8 = 12,870 cases. The even permutation required gives a extra factor of 2.

The overall space of this stage is 56,980 * 12,870 * 2 = 1,466,665,200.

                     Slice turns
               ------------------------
    distance   positions         unique
    --------   ---------         ------
       0               6              6
       1              12              4
       2             150             28
       3           1,556            230
       4          16,310          2,185
       5         169,240         21,630
       6       1,717,460        216,142
       7      16,888,105      2,115,779
       8     155,841,738     19,496,147
       9   1,219,752,205    152,510,075
      10   5,364,611,902    670,664,810
      11   4,687,652,572    586,031,875
      12     147,926,722     18,500,776
      13           5,021            732
      14               1              1
          --------------  -------------
          11,594,583,000  1,466,665,200

Stage 4

The goal is to put corners into one of the 96 configurations that can be solved using only half-turn moves, put U and D centers into one of the 12 configurations that can be solved using only half-turn moves and put all U- and D-layer edges into a configuration that can be solved using only half-turn moves. This consists of 96 possible configurations for the l- and r-layer edges, and 96 for the f- and b-layer edges.

Turns allowed:

    U, U',U2, u2, D, D', D2, d2,
          L2, l2,        R2, r2,
          F2, f2,        B2, b2

The corner coordinate is exactly like the edge coordinate from stage 2, which gives 420 cases.

The remaining centers are already in the right faces, so we only need to put them in the right order: C^8_4 = 70. Using the same trick as for stage 2 and 3, we only need to keep 35 cases.

The edges are as the corners, except that there are two groups of edges so 420 * 420 = 176,400. In fact, only half of the cases happen, because of the parity condition from stage 3, so 88,200 real cases. We are doing the symmetry reduction on this coordinate (16 symmetries), which leave only 5,968 cases. Again, there is no benefit from adding cube rotations in the reduction, so we have S1 = D4h (all symmetries that preserve the UD axis) and S2 = C1 ({id}).

The overall size is 420 * 35 * 5,968 = 87,729,600

                     Slice turns
               ------------------------
    distance   positions         unique
    --------   ---------         ------
       0              12              4
       1              24              3
       2             204             12
       3           1,280             40
       4           7,548            171
       5          40,964            899
       6         227,816          4,528
       7       1,259,844         21,918
       8       6,912,088        108,036
       9      35,259,020        534,374
      10     152,072,296      2,417,720
      11     466,530,500      8,958,735
      12     759,591,796     23,141,105
      13     738,648,672     30,826,779
      14     387,337,472     14,255,009
      15      45,079,256      1,014,899
      16         111,144          1,988
           -------------    -----------
           2,593,080,000     81,286,220

Stage 5

The goal is to put all cubies into their solved position.

Turns allowed:

    U2, u2, D2, d2,
    L2, l2, R2, r2,
    F2, f2, B2, b2

There are 96 positions for corners.

Edges are like 3 independent groups of corners, so 96 * 96 * 96 = 884,736 positions. We are doing a symmetry reduction on this coordinate. This subgroup has all 48 symmetries, so we can conjugate using the group M. However, the cube can be in four different solved positions as F/B, R/L and U/D colours can be swapped. So we add to the 48 conjugated symmetries 4 cube rotations (generated by x2 and y2), giving S1 = M and S2 = D2 (face). This gives only 7,444 sym-coordinates for edges.

For centers, each pairs of opposite centers have 12 different configurations, so 12*12*12 = 1,728 positions.

The overall size is 96*7,444*1,728 = 1,234,870,272

                     Slice turns
               --------------------------
    distance    positions          unique
    --------    ---------          ------
       0                4               1
       1               48               2
       2              420               7
       3            3,456              36
       4           27,168             228
       5          203,752           1,429
       6        1,451,996           9,127
       7        9,527,856          55,967
       8       56,528,036         320,517
       9      295,097,696       1,636,219
      10    1,306,291,304       7,145,262
      11    4,761,203,264      25,797,686
      12   13,820,728,272      74,257,367
      13   29,956,341,744     159,930,965
      14   43,427,866,752     231,079,243
      15   36,297,535,208     193,022,572
      16   14,711,566,720      78,368,608
      17    2,063,584,704      11,055,492
      18       59,082,112         320,252
      19           45,056             244
          ---------------   -------------
          146,767,085,568     783,001,224