# Solving the 4x4x4 in 85 twists

In my posting titled "The 4x4x4 can be solved in 79 moves (STM)," I reported about an analysis I did where the 4x4x4 cube is solved in five stages. In that analysis, a move was considered to be any quarter-turn or half-turn of a single slice.

I have now completed a similar analysis of the 4x4x4 cube where a move is considered to be any quarter- or half-turn twist of the cube, and where a twist is considered to be one portion of the cube (a face layer, or a block consisting of a face layer and the adjacent inner layer) being turned with respect to the rest of the cube. The analysis indicates that any valid position of the 4x4x4 cube can be solved via these five stages using no more than 85 twists.

See the other article for more details about the five stages. Here, I'll simply list the various moves allowed to be used in each stage.

Stage 1
Twists allowed:
U,U',U2,(Uu),(Uu)',(Uu)2, D,D',D2,(Dd),(Dd)',(Dd)2,
L,L',L2,(Ll),(Ll)',(Ll)2, R,R',R2,(Rr),(Rr)',(Rr)2,
F,F',F2,(Ff),(Ff)',(Ff)2, B,B',B2,(Bb),(Bb)',(Bb)2
One-time whole cube rotations allowed:
120-degree turns (either direction) about the UFL-DBR axis.

Stage 2
Twists allowed:
U,U',U2,(Uu),(Uu)',(Uu)2, D,D',D2,(Dd),(Dd)',(Dd)2,
L2,(Ll)2, R2,(Rr)2,
F2,(Ff)2, B2,(Bb)2
Inner slice turns allowed (counted as two twists):
f,f',b,b'
One-time whole cube rotations allowed:
90-degree turn about U-D axis.
Note that this stage allows inner slice turns in order for it to be possible to solve all positions of this stage while also not allowing any invalid positions for this stage to be reachable. But since inner slice turns require twisting the cube in two places, these turns are counted as two twists.

Stage 3
Twists allowed:
U,U',U2,(Uu)2, D,D',D2,(Dd)2,
L2,(Ll)2, R2,(Rr)2,
F2,(Ff)2, B2,(Bb)2
Inner slice turns allowed (counted as two twists):
f,f',b,b'
This stage allows the same inner slice turns as allowed in stage 2. Note that these four inner slice turns are the only turns allowed in this stage that are not allowed in the next stage. That means that one of these moves is always the last move of this stage. But since these moves are always counted as 2 twists, this stage has no positions of distance 1.

Stage 4
Twists allowed:
U,U',U2,(Uu)2, D,D',D2,(Dd)2,
L2,(Ll)2, R2,(Rr)2,
F2,(Ff)2, B2,(Bb)2

Stage 5
Twists allowed:
U2,(Uu)2, D2,(Dd)2,
L2,(Ll)2, R2,(Rr)2,
F2,(Ff)2, B2,(Bb)2
One-time whole cube rotations allowed:
180-degree turns about U-D, F-B, L-R axes.

The results of the analyses of the five stages is given below. I have computed results in terms of total positions as well as positions that are unique with respect to applicable symmetries of the cube.

```Stage 1

distance   positions           unique
0               3                2
1               6                2
2             108               11
3           1,932              136
4          31,218            2,000
5         463,422           29,136
6       6,029,550          377,432
7      62,063,820        3,880,774
8     383,382,798       23,965,573
9     849,606,252       53,106,043
10     303,401,406       18,965,318
11       3,494,562          218,585
-------------      -----------
1,608,475,077      100,545,012

Stage 2

distance   positions           unique
0               24               14
1               24                6
2              168               30
3            1,200              185
4            8,140            1,129
5           56,178            7,341
6          367,100           46,777
7        2,302,670          289,977
8       14,124,912        1,770,189
9       81,750,306       10,228,545
10      417,018,176       52,143,753
11    1,634,702,952      204,363,892
12    3,979,487,116      497,483,783
13    5,732,083,942      716,574,370
14    5,573,127,792      696,690,156
15    3,330,770,724      416,371,475
16      815,661,700      101,967,538
17       40,568,480        5,073,399
18          813,084          101,862
19            2,712              389
-------------      -----------
21,622,847,400    2,703,114,810

Stage 3

distance   positions           unique
0                12               7
1                 0               0
2                24               6
3               240              37
4             1,628             249
5            12,432           1,659
6            84,596          10,884
7           516,020          65,214
8         2,904,664         364,740
9        15,341,866       1,921,737
10        81,949,156      10,251,916
11       461,971,534      57,764,972
12     2,221,037,592     277,666,652
13     6,858,548,392     857,379,146
14     8,906,738,640   1,113,405,703
15     4,086,085,086     510,797,506
16       532,101,222      66,522,880
17        21,780,108       2,724,445
18            92,746          11,656
19                42              11
--------------   -------------
23,189,166,000   2,898,889,420

Stage 4

distance    positions          unique
0                12               5
1                24               4
2               156              18
3               816              67
4             4,336             309
5            24,776           1,690
6           132,432           8,747
7           670,284          43,041
8         3,382,304         214,202
9        16,909,008       1,064,081
10        76,851,572       4,822,940
11       285,480,696      17,888,097
12       738,430,708      46,230,114
13       984,159,264      61,595,705
14       454,803,540      28,476,121
15        32,176,504       2,022,258
16            53,568           3,733
-------------     -----------
2,593,080,000     162,371,132

Stage 5

distance    positions          unique
0                4               2
1               36               5
2              252              15
3            1,728              70
4           11,528             374
5           72,300           1,988
6          431,188          10,423
7        2,459,832          55,600
8       13,361,660         291,127
9       68,407,980       1,464,351
10      326,021,992       6,914,502
11    1,414,642,236      29,844,904
12    5,361,506,980     112,742,406
13   16,520,565,624     346,616,171
14   36,467,453,404     764,073,198
15   47,828,766,672   1,002,434,703
16   30,852,487,408     648,178,826
17    7,546,175,832     159,746,983
18      362,229,856       8,020,105
19        2,450,544          67,417
20           38,512           1,862
---------------   -------------
146,767,085,568   3,080,465,032

```

The number of twists required (worst case) for each stage are 11, 19, 19, 16, and 20, respectively. Thus, any position of the 4x4x4 can be solved using no more than 85 twists.

## Comment viewing options

### Make that 83 twists

During the process of trying out the 85-twist, five-stage procedure for solving the 4x4x4, I noticed that the generated solutions for random scrambles contained twist sequences that could obviously be optimized. While this was to be expected across stage boundaries, there were such sequences that were not across a stage boundary. These were three-twist sequences that could be shortened to two twists. For example, F2 and f are allowable single-slice turns for stages 2 and 3. The combination (F2 f) could be achieved by substituting (Ff) F' for f, so (F2 f) could be done as three twists, F2 (Ff) F'. Of course, the same can be done with only two twists, (Ff) F.

Thus, I have now done a new calculation for stages 2 and 3 that allow the following double-twist moves along with the other moves allowed before:
(Ff) F = F2 f
(Ff)' F' = F2 f'
(Bb) B = B2 b
(Bb)' B' = B2 b'

Of course, these double-twists count as 2 twists.

The result of these analyses reduces the maximum number of twists for these stages from 19 to 18 for each stage. This reduces the upper bound to solve the 4x4x4 from 85 to 83. The summary for these analyses is given below.

```Stage 2

distance   positions           unique
0               24               14
1               24                6
2              168               30
3            1,296              197
4            9,564            1,307
5           70,402            9,136
6          495,508           62,895
7        3,369,218          423,478
8       22,165,448        2,775,775
9      136,299,902       17,047,938
10      711,992,120       89,016,697
11    2,580,017,520      322,533,475
12    5,239,924,216      655,047,340
13    6,401,953,318      800,311,196
14    4,936,417,944      617,095,579
15    1,489,502,272      186,205,974
16       99,551,228       12,448,635
17        1,074,172          134,686
18            3,056              452
-------------      -----------
21,622,847,400    2,703,114,810

Stage 3

distance   positions           unique
0               12                7
1                0                0
2               24                6
3              240               37
4            1,628              249
5           12,816            1,707
6           91,220           11,712
7          588,372           74,258
8        3,577,144          448,878
9       20,949,282        2,623,065
10      123,046,976       15,390,083
11      715,681,378       89,480,692
12    3,354,929,964      419,408,897
13    8,955,143,808    1,119,461,407
14    7,831,924,984      979,053,519
15    2,108,992,906      263,651,195
16       68,139,010        8,521,984
17        6,085,140          761,574
18            1,096              150
--------------    -------------
23,189,166,000   2,898,889,420
```