# 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
```

## Comment viewing options

### It's nice to see my results i

It's nice to see my results independently verified after all these years. Thanks, Clement.

I note that my corrected stage 2 table can be found here, just in case someone is thinking there is a mismatch on that stage.

It appears that Clement's post is missing distance 17 on the stage 4 table. The values in the positions column do not add up to the given total, and the values all agree with mine except for the missing distance 17. Since his "unique" column adds up to the given total, I would guess the real total is little bit higher.

### Re: Bruce's 4x4x4 Program

First, a quick re-introduction, since I now know how "The artist formerly known as Prince" must have felt after renaming himself. I was formerly known as "Unsolved" on Speedsolving.com because... quite simply, my 4x4x4 program could not solve a randomly scrambled cube from start to finish.

So now I am on here as NoLongerUnsolvedButSolved, but for a slightly different reason. I "upgraded" to work on the 5x5x5 cube, and I am happy to announce that it CAN solve even sufficiently randomized scrambles from start to finish.

I have an older copy of Bruce's 4x4x4 Brute Force version of his solving program, and I am wondering if there have been any updates to it in the past year, or if his 5-stage version has been improved? I see Clement has made some posts about half a year ago along similar lines. I'd like to run Bruce's program on my new hardware and see how fast it cruises along.

Hopefully Bruce will get this message at some point. And if anyone needs to run any programs on a really fast Windows system with 128 GB of RAM, let me know. Always happy to help.

### Correction regarding stage 4 distance table

Yes, I forgot to tell that I was using the extended stage 2 where you are allowed all 12 inner quarter turns.

About stage 4 distance table, this is a regrettable copy/paste mistake. Here is the correct distance table:
```                     Slice turns
------------------------
distance   positions         unique
--------   ---------         ------
0               6              4
1              12              3
2             102             12
3             640             56
4           3,774            285
5          20,482          1,475
6         113,908          7,655
7         629,922         40,711
8       3,456,044        219,404
9      17,629,510      1,110,842
10      76,036,148      4,774,517
11     233,265,250     14,621,516
12     379,795,898     23,799,062
13     369,324,336     23,143,536
14     193,668,736     12,142,383
15      22,539,628      1,420,768
16          55,572          3,983
17              32              8
-------------    -----------
1,296,540,000     81,286,220
```