# Refining Bruce Norskog's 4x4x4 five stage analysis

Submitted by Clement Gallet on Fri, 12/11/2015 - 08:03.

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:

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.

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:

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

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:

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.

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:

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

Stage 5

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

Turns allowed:

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

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', b2There 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', b2As 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', b2For 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, b2The 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, b2There 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

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

### Re: Bruce's 4x4x4 Program

Submitted by NoLongerUnsolve... on Fri, 06/03/2016 - 23:17.

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.

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

Submitted by Clement Gallet on Fri, 12/18/2015 - 07:18.

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:

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

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