# The 4x4x4 can be solved in 79 moves (STM)

I have done a five-stage analysis of the 4x4x4 cube. My analysis considers the four centers for each face to be indistinguishable. It also assumes that there is no inner 2x2x2 cube in the middle of the cube.

Like Morwen Thistlethwaite's well-known four-stage 3x3x3 analysis, my five-stage procedure consists of multiple stages where each successive stage only allows use of a subset of the moves allowed in the previous stage, with the final stage only allowing half turns. So far, I have completed analyses of the five stages using the slice turn metric (STM). Use of other metrics is possible. (In fact I have done some other metrics for some of the stages.) My analyses for each individual stage are optimal with respect to the specified move restrictions for each stage. The results indicate that the 4x4x4 can be solved using a maximum of 79 slice turns.

Unlike the 3x3x3 cube, the 4x4x4 does not have fixed centers that provide a reference for the slices or layers of the cube. When the positions of the 4x4x4 cube are counted, it is usually considered that it doesn't matter how the cube is oriented. For example, the solved cube can have any of its six faces facing up, and then any of four faces can be selected as the front face, for a total of total of 24 possible ways to orient the cube.

So there is a question, given some position of the cube, how do you define what face does the move U (conventionally refers to a clockwise quarter-turn of the top layer) do? If you're allowed to choose any of the 24 orientations of that position, "U" could mean a clockwise quarter-turn of any of the six faces. Clearly, if we want to have stages in the analysis where we want to allow the move U, but not the move L (clockwise quarter-turn of the left face) or F (clockwise quarter-turn of the front face), we need to consider that the cube has some fixed orientation. That is, we need to consider that the cube is viewed with respect to some fixed reference, and the same position, but in different orientations, are really considered to be separate positions.

However, it should be intuitive that no matter what orientation the cube is in, the number of moves required to solve it is the same. The orientation of the cube essentially only affects how we refer to the moves. Thus, my algorithm allows solving some particular stages in the "wrong" orientation, and then allows a whole cube rotation (or change in reference frame) to make it properly oriented for the next stage. Of course, whole cube rotations can not be allowed that destroy some aspect of the state of the cube that is required by the following stage. For example, the first stage will orient the corner cubies. All subsequent stages assume that the orientation of the corner cubies that was achieved in the first stage will be retained, so no whole cube rotations can be permitted afterwards that would disrupt that orientation state of the corner cubies.

Notation: For the moves, I will use:

U = clockwise quarter-turn of the top ("up") slice or layer

D = clockwise quarter-turn of the bottom ("down") slice or layer

u = clockwise quarter-turn of the upper inner slice

d = clockwise quarter-turn of the lower inner slice

L = clockwise quarter-turn of the left-hand outer slice

R = clockwise quarter-turn of the right-hand outer slice

l = clockwise quarter-turn of the left-hand inner slice

r = clockwise quarter-turn of the right-hand inner slice

F = clockwise quarter-turn of the front outer slice

B = clockwise quarter-turn of the back outer slice

f = clockwise quarter-turn of the front inner slice

b = clockwise quarter-turn of the back inner slice

The corresponding counter-clockwise quarter-turns are donated with an apostrophe (') after the letter.

The corresponding half-turns are donated using a '2' after the letter.

I will also use these letters to refer to the positions of the respective layers within the cube.

Now I will describe the five stages I have used.

Stage 1

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

All slice 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

One-time whole cube rotations allowed:

120-degree turns (either direction) about the UFL-DBR axis.

Stage 2

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

Slice turns allowed:

U,U',U2,u,u',u2,D,D',D2,d,d',d2,

L2,l2,R2,r2,

F2,f,f',f2,B2,b,b',b2

One-time whole cube rotations allowed:

90-degree turn about U-D axis.

Stage 3

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.
This leaves the centers for the U and D faces arbitrarily arranged in the U and D faces.
Put top and 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.

Slice turns allowed:

U,U',U2,u2,D,D',D2,d2,

L2,l2,R2,r2,

F2,f,f',f2,B2,b,b',b2

Stage 4

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

Slice turns to use:

U,U',U2,u2,D,D',D2,d2,

L2,l2,R2,r2,

F2,f2,B2,b2

Stage 5

Put all cubies into their solved position.

Slice turns allowed:

U2,u2,D2,d2,

L2,l2,R2,r2,

F2,f2,B2,b2

180-degree turns about U-D, F-B, L-R axes.

The results of the analyses of the five stages is given below. In some cases, I have also computed results in terms of positions that are unique with respect to applicable symmetries of the cube.

Stage 1 Slice turns ------------------------ distance positions unique -------- --------- ------ 0 3 2 1 6 2 2 144 12 3 2,796 193 4 48,324 3,088 5 745,302 46,791 6 10,030,470 627,576 7 103,416,912 6,465,575 8 575,138,592 35,951,459 9 826,559,202 51,665,935 10 92,489,544 5,781,632 11 43,782 2,747 ------------- ----------- 1,608,475,077 100,545,012 Stage 2 Slice turns ------------------------ distance positions unique -------- --------- ------ 0 24 14 1 48 11 2 684 99 3 7,338 997 4 68,276 8,824 5 614,616 78,097 6 5,372,580 675,305 7 41,587,696 5,206,350 8 264,525,432 33,076,413 9 1,173,434,250 146,693,452 10 2,891,653,248 361,482,039 11 4,023,107,440 502,932,549 12 4,610,360,196 576,354,995 13 4,818,898,672 602,411,843 14 2,904,398,972 363,077,183 15 804,769,384 100,607,241 16 82,031,496 10,256,713 17 2,007,656 251,493 18 9,392 1,192 ------------ ------------- 21,622,847,400 2,703,114,810 Stage 3 Slice turns ------------------------ distance positions unique -------- --------- ------ 0 12 7 1 24 6 2 300 47 3 3,112 427 4 32,620 4,241 5 338,480 42,806 6 3,434,920 430,920 7 33,776,210 4,227,153 8 311,683,476 38,977,409 9 2,439,504,410 304,981,049 10 10,729,223,804 1,341,243,036 11 9,375,305,144 1,171,989,581 12 295,853,444 36,991,377 13 10,042 1,360 14 2 1 -------------- ------------- 23,189,166,000 2,898,889,420 Stage 4 Slice turns ----------- distance positions -------- --------- 0 12 1 24 2 204 3 1,280 4 7,548 5 40,964 6 227,816 7 1,259,844 8 6,912,088 9 35,259,020 10 152,072,296 11 466,530,500 12 759,591,796 13 738,648,672 14 387,337,472 15 45,079,256 16 111,144 17 64 ------------- 2,593,080,000 Stage 5 ("Squares Coset") Slice turns -------------------------- distance positions unique -------- --------- ------ 0 4 2 1 48 6 2 420 23 3 3,456 124 4 27,168 806 5 203,752 5,197 6 1,451,996 33,853 7 9,527,856 211,333 8 56,528,036 1,223,997 9 295,097,696 6,305,655 10 1,306,291,304 27,704,719 11 4,761,203,264 100,510,701 12 13,820,728,272 290,661,124 13 29,956,341,744 628,414,595 14 43,427,866,752 910,241,690 15 36,297,535,208 761,210,397 16 14,711,566,720 309,104,278 17 2,063,584,704 43,573,552 18 59,082,112 1,262,024 19 45,056 956 --------------- ------------- 146,767,085,568 3,080,465,032

The number of slice turns required (worst case) for each stage are 11, 18, 14, 17, and 19, respectively. Thus, any position of the 4x4x4 can be solved in at most 79 slice turns.

I have created a program that took 200 random cubes and solved them directly using distance tables created from the above analyses. The program verified each one being correctly solved. Of these 200 cases, 64 was the highest number of slice turns that were required by the program to solve the cube. (And that case could be trivially reduced to 63 by removing a redundancy with respect to moves spanning a stage boundary.)

I would like to thank Mark Longridge who suggested doing an analysis of this type for the 4x4x4. I would also acknowledge Morwen Thistlethwaite who performed the original 3x3x3 analysis from which the idea for this analysis originates.