Home »

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

Submitted by Bruce Norskog on Sun, 07/09/2006 - 18:38.

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

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

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

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

Stage 4 details and symmetry-reduced results

Submitted by Bruce Norskog on Wed, 07/19/2006 - 21:36.

I had calculated symmetry-reduced numbers for each of the 5 stages in my analysis, except the fourth stage. So I have now calculated symmetry-reduced values for Stage 4. Since this stage had a "mere" 2,593,080,000 positions, I did my initial analysis of it without going to the trouble of using symmetry to reduce the number of positions. Since 16 of the 48 elements of the symmetry group of the cube are applicable to Stage 4, the total number of positions can be reduced almost 16x using symmetry. The results are given below. Following that, I discuss Stage 4 in more detail.

Stage 4

                 Slice turns
           ------------------------
distance   positions         unique
--------   ---------         ------
   0              12              5
   1              24              4
   2             204             19
   3           1,280             97
   4           7,548            527
   5          40,964          2,783
   6         227,816         14,852
   7       1,259,844         80,308
   8       6,912,088        436,088
   9      35,259,020      2,214,786
  10     152,072,296      9,531,856
  11     466,530,500     29,208,755
  12     759,591,796     47,546,251
  13     738,648,672     46,237,953
  14     387,337,472     24,256,088
  15      45,079,256      2,833,318
  16         111,144          7,430
  17              64             12
       -------------    -----------
       2,593,080,000    162,371,132

While Stage 4 had only a "small" number of positions, I had some difficulty defining precisely what those positions are. It was the edge cubies that I had a difficult time with. For Stage 4, the sixteen edge cubies in the top and bottom layers of the cube are the edge cubies that matter. In Stage 3, they are separated out into eight "left-handed" cubies and eight "right-handed" cubies. So there are 8! possible positions of the left-handed cubies and 8! possible positions of the right-handed cubies. Since the cubies must be in an even permutation, only half the positions are allowed, so there are a total of (8!2)/2 or 812,851,200 possible permutations of these sixteen edge cubies. In Stage 4, we need to put these cubies into a configuration that can be solved with only half-turns. There are 962 or 9,216 such configurations. Therefore, for Stage 4, we should be able to define the edge positions as cosets each containing 9,216 permutations. So the number of edge positions needed for Stage 4 is 812,851,200/9,216 or 88,200.

I then proceeded to figure out a way to efficiently convert each of the 812,851,200 allowable permutations of the edge cubies to the proper one of 88,200 representative positions. I then built a hash table to store the 88,200 representatives, along with an index number, so I could efficiently convert a representative into a number from 0 to 88,199. Then I could use these two steps to somewhat efficiently convert any of the 812,851,200 permutation values into a "coordinate" value from 0 to 88,199. Perhaps there is a more elegant way this could be done, but this at least well enough to get the analysis done.

The corners had 8! possible permutations, and needed to be put into one of 96 configurations that can be solved using only half-turns. Thus, there were 8!/96 or 420 cosets for the corner positions. A table used for Stage 2 edges could be used to map the 40,320 permutations to one of the 420 Stage 4 corner positions.

There are 8!/(4!2) or 70 possible configurations for the top and bottom centers within those two faces. While there are 12 configurations that are considered solved as far as Stage 4 is concerned, since the centers don't form a group, I simply treated the centers as having 70 possible positions. This results in a total of 88,200 * 420 * 70 or 2,593,080,000 positions for Stage 4.

For more information on the analyses of the other stages, see my post entitled 'God's algorithm calculations for the 4x4x4 "squares set"' and its follow-up posts.

» login or register to post comments