God's algorithm calculations for the 4x4x4 "squares set"

Thank you for that explanation, Jaap. By the way, I would also like to say that I frequently look to your web site for information, and very much appreciate your web site.

A few months ago, in a reply to Jaap's post about solving the centers (centres) of the 4x4x4, Mark suggested attempting to extend Thistlethwaite's algorithm to the 4x4x4.I've been looking at this, and have come up with the following plan for solving the 4x4x4 in five stages. The squares coset analysis already given represents the fifth stage of this 5-stage procedure. It is possible the following description might need some minor corrections. If so, feel free to explain what you think needs to be corrected.

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.)
One-time whole cube rotations: 120-degree turns (either direction) about the UFL-DBR axis.
Slice turns to use:
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

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 square 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 square moves.
One-time whole cube rotations: 90-degree turn about U-D axis.
Slice turns to use:
U,U',U2,u,u',u2,D,D',D2,d,d',d2,
L2,l2,R2,r2,
F2,f,f',f2,B2,b,b',b2

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 square moves. Put centers for the U and D faces into 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.
Slice turns to use:
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 square moves. Put U and D centers into one of the 12 configurations that can be solved using only square moves. Put all U- and D-layer edges into a configuration that can be solved using only square 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 solved position.
One-time whole cube rotations: 180-degree turns about U-D, F-B, L-R axes.
Slice turns to use:
U2,u2,D2,d2,
L2,l2,R2,r2,
F2,f2,B2,b2

I have already been working on stage 1. If anyone is interested in working on any of the other stages, reply here. Otherwise, I will probably just continue on to stage 2, stage 3, and then stage 4 as I have time.

I have results for stage 1 of my plan for solving the 4x4x4 in five stages. This stage starts with an arbitrary (legal) 4x4x4 position. The goal of the stage is to orient the corner cubies (so the U or D facelet faces up or down) and to put the u- and d-layer edges somewhere in those two layers. The center cubies are ignored in this stage. There are 3^7 = 2187 possibilities for the orientation of the eight corner cubies. There are 24!/(16!*8!) = 735471 combinations of placing a set of eight edge cubies (considered indistinguishable at this stage) among the 24 edge positions. So this stage has a total of 2,187*735,471 = 1,608,475,077 positions. The stage can be considered to include a one-time rotation of the whole cube (not counted as a move) so that the stage can be completed with what should be the "up" face facing a different direction. Because of symmetry, it appears to me only three orientations matter. So there are considered to be three solved states.

As with the squares coset analysis, I have not only used the slice-turn metric, but also have done analyses for "twist turns" and "block turns" as well. For this stage, of course, I needed to consider quarter-turns as well as half-turns. I also change my definition for block turns to include moving a 4x4x3 block with respect to the rest of the cube. So the set of moves I used for each metric is listed below:

Slice turns:
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

Twist turns:
U, U', U2, D, D', D2, (U u), (U u)', (U2 u2), (D d), (D d)', (D2 d2),
(U u d'), (U' u' d), (U2 u2 d2), (D d u'), (D' d' u), (D2 d2 u2),
L, L', L2, R, R', R2, (L l), (L l)', (L2 l2), (R r), (R r)', (R2 r2),
(L l r'), (L' l' r), (L2 l2 r2), (R r l'), (R' r' l), (R2 r2 l2),
F, F', F2, B, B', B2, (F f), (F f)', (F2 f2), (B b), (B b)', (B2 b2),
(F f b'), (F' f' b), (F2 f2 b2), (B b f'), (B' b' f), (B2 b2 f2)

Block turns:
Includes the union of the slice turns and twist turns, and also:
(u d'), (u' d), (u2 d2),
(l r'), (l' r), (l2 r2),
(f b'), (f' b), (f2 b2)

I did the analyses without using symmetry reductions, so I don't have symmetry-reduced numbers available. At this point, I haven't done much to verify the results, so I am not yet totally confident in the results.

4x4x4 stage 1

distance slice turns    twist turns    block turns
-------- -----------    -----------    -----------
    0              3              3              3
    1              6              6              6
    2            156            228            336
    3          3,560          8,463         13,806
    4         70,636        286,922        519,157
    5      1,237,252      7,739,249     15,833,805
    6     18,075,027    140,009,317    275,936,444
    7    178,452,186    850,633,007  1,029,284,931
    8    715,636,485    602,898,722    286,686,684
    9    639,448,150      6,899,160        199,905
   10     55,545,380
   11          6,236
       -------------   ------------  -------------
       1,608,475,077  1,608,475,077  1,608,475,077

I believe I now have correct results for stage 1 of my proposed 5-stage solution for the 4x4x4 cube. I have now also computed the number of positions that are unique with respect to the 16 symmetries of the cube that are relevant to this analysis.

4x4x4 Stage 1 analysis

                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

                twist turns                   block turns
          ------------------------      ------------------------
distance  positions         unique      positions         unique
   0              3              2              3              2
   1              6              2              6              2
   2            108             11            216             23
   3          1,932            136          5,250            371
   4         31,218          2,000        111,444          7,112
   5        463,422         29,136      2,118,252        132,814
   6      6,029,550        377,432     32,552,448      2,036,017
   7     62,063,820      3,880,774    311,018,796     19,443,181
   8    383,382,798     23,965,573    945,744,666     59,115,320
   9    849,606,252     53,106,043    315,640,704     19,729,932
  10    303,401,406     18,965,318      1,283,292         80,238
  11      3,494,562        218,585              0              0
      -------------    -----------  -------------    -----------
      1,608,475,077    100,545,012  1,608,475,077    100,545,012

I've now also done stage 1 analyses using only quarter turns.

For clarity, the following lists define what I mean by the terms slice quarter-turns, twist quarter-turns, and block quarter-turns. I've not included moves of 4x4x3 blocks here, since these are in effect redundant with face turns.

Slice quarter-turns:
U,U',u,u',D,D',d,d',
L,L',l,l',R,R',r,r',
F,F',f,f',B,B',b,b'

Twist quarter-turns:
U,U',D,D',(U u),(U u)',(D d),(D d)',
L,L',R,R',(L l),(L l)',(R r),(R r)',
F,F',B,B',(F f),(F f)',(B b),(B b)'

Block quarter-turns:
U,U',u,u',D,D',d,d',(U u),(U u)',(D d),(D d)',(u d'),(u' d),
L,L',l,l',R,R',r,r',(L l),(L l)',(R r),(R r)',(l r'),(l' r),
F,F',f,f',B,B',b,b',(F f),(F f)',(B b),(B b)',(f b'),(f' b)

            slice quarter turns
        --------------------------

distance  positions         unique
--------  ---------         ------
   0              3              2
   1              6              2
   2             96              6
   3          1,416             98
   4         16,872          1,069
   5        189,324         11,900
   6      1,979,916        123,914
   7     18,083,490      1,130,772
   8    124,919,346      7,809,155
   9    496,644,282     31,044,284
  10    735,316,956     45,962,786
  11    225,406,314     14,090,907
  12      5,916,864        370,105
  13            192             12
      -------------    -----------
      1,608,475,077    100,545,012

            twist quarter turns           block quarter turns
        --------------------------    --------------------------

distance  positions         unique      positions         unique
--------  ---------         ------      ---------         ------
   0              3              2              3              2
   1              6              2              6              2
   2             72              5            144             11
   3          1,044             72          2,952            197
   4         11,076            702         47,268          3,007
   5        114,300          7,196        686,970         43,050
   6      1,174,608         73,559      8,774,946        548,899
   7     10,639,320        665,492     84,204,966      5,264,307
   8     75,344,742      4,710,401    444,840,750     27,806,624
   9    339,690,198     21,233,782    794,156,340     49,640,245
  10    703,609,584     43,980,444    268,019,748     16,754,428
  11    432,863,106     27,057,913      7,739,808        484,162
  12     44,831,274      2,803,112          1,176             78
  13        195,744         12,330              0              0
      -------------    -----------  -------------    -----------
      1,608,475,077    100,545,012  1,608,475,077    100,545,012

I finally have results for stage 2 of my plan for solving the 4x4x4 in five stages.

This stage starts with the corners oriented (so the U or D facelet faces up or down), the u- and d-layer edges somewhere within those two layers, and the centers arbitrarily arranged. The goal of this stage is to put the 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 to arrange the 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. In this stage, it is only necessary to consider the positions of the u- and d-layer edges, and the positions of the front and back centers. Since the u- and d-layer edges are constrained to the u and d layers, there are 8! or 40320 possible arrangements of these edges. The number of these positions that are considered solved as far as this stage is concerned is 96. The calculations for this stage were simplified by considering that the edges must be in one of 40320/96 = 420 equivalence classes. The front and back centers can be in one of ((24*23*22*21)/24)*((20*19*18*17)/24) = 51,482,970 arrangements. Of these, 12 are considered to be "solved" as far as this stage is concerned. I had hoped this would mean only 51,482,970/12 equivalence classes would be needed, but this is not the case. (That isn't even an integer.) So I considered all 51,482,970 center configurations in the analysis. This makes the total positions for this stage 420*51,482,970 = 21,622,847,400. Since this is a rather large number, I used a sym-coordinate for the edge equivalence classes. With 8 applicable symmetries, the 420 edge equivalence classes could be reduced to 98. Thus, the analysis was done using a "coordinate space" of 98*51,482,970 = 5,045,331,060 elements. Stage 2 allows one whole cube rotation of 90 degrees about the U-D axis, so the analysis uses 24 distance-0 positions rather than 12. (1 edge equivalance class, 12 center configurations, 2 cube orientations)

With 1GB of RAM in my computer, I used only 1 bit per element in the main array, or about 630 million bytes. I also used 98 disk files, with each file storing distances for the set of 51482970 center configurations for a representative edge equivalence class. I used 4-bit distances to pack two distance values to a byte. Since the maximum distance turned out to be 18, this turned out to be insufficient, but I was able to work around that problem.

The disk files would be processed one at a time, looking for positions of the previously determined distance, and then positions 1 move from those positions would be found. The main array would keep track of these positions. After processing all 98 files, the positions in the main array marked as being reached were checked against the files to see which ones were actually formerly at an unknown distance. A new set of 98 files updated for this new distance would be written during this process.

I've only done the analysis for the slice turn metric for stage 2. The slice turns used in this stage was restricted so that positions reached would remain within the set of goal state positions of stage 1. These moves are:

4x4x4 Stage 2 analysis

                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

I now have results for stage 3 of my plan for solving the 4x4x4 in five stages.

This stage starts with the corners oriented (so the U or D facelet faces up or down), the u- and d-layer edges are in those layers in one of the configurations that can be solved using only half-turns, and the F and B centers are in one of the twelve configurations that can be solved using only half-turns. The goal of this stage is to place the l-, r-, f-, and b-layer edges so that the top or bottom facelet is facing up or down, and to place the L and R centers into the left and right faces in one of the twelve configurations that can be solved using only half-turns. (This leaves the U and D centers to be arranged in some arbitrary manner within the top and bottom layers. I note that each stage preserves what has been accomplished by the previous stages.)

In this stage, it is only necessary to consider what happens to the l-, r-, f-, and b-layer edges (which are also the top and bottom layer edges) and the centers for the left and right faces (which may be located within the left, right, top, and bottom faces). The l-, r-, f-, and b-layer edges can be divided into two sets of eight, depending on which locations they can occupy when their U or D facelet is "oriented." Thus, as far as the edges for this stage are concerned, it is only necessary to know the combination of positions occupied by one of the sets of eight cubies. Thus, there are a total of 16!/(8!*8!) = 12,870 edge positions for this stage.

For the centers, we only are concerned with where the left-face and right-face centers are located, and they are known to be in the left, right, top, and bottom faces in this stage. So the number of center positions in this stage is (16!/(12!*4!))*(12!/(8!*4!)) = 900,900.

Thus, the total number of positions in this stage is 12,870*900,900 = 11,594,583,000. Symmetry can be used to reduce the total number of "unique" positions. It is possible to use eight of the 48 symmetries of the cube to reduce the number of edge positions from 12,870 to 1763. This reduces the 11,594,583,000 positions to a "coordinate space" of 1763*900,900 = 1,588,286,700 positions, of which 1,449,444,710 are unique with respect to the symmetries used.

I used two bits per coordinate space position in memory, and created a disk file containing 4 bits per coordinate space position so that the disk file directly gives the distance for each of the 1,449,444,710 representatives.

As with stage 2, I've only done the analysis for stage 3 in the slice turn metric. The slice turns used in this stage was restricted so that positions reached would remain within the set of goal state positions of stage 2. These moves are:
U, U', U2, u2, D, D', D2, d2,
L2, l2, R2, r2,
F2, f, f', f2, B2, b, b', b2

4x4x4 Stage 3 analysis

                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,192         42,764
  6       3,422,856        429,378
  7      33,301,210      4,167,562
  8     296,684,804     37,101,001
  9   2,069,017,694    258,660,323
 10   6,422,550,196    802,864,880
 11   2,752,074,608    344,028,608
 12      17,157,252      2,145,448
 13             120             18
       ------------  -------------
     11,594,583,000  1,449,444,710

I have realized that I did Stage 3 incorrectly. The problem is that I did not describe what stage 3 does correctly. I introduce a modified description for Stage 3, and provide the results for this corrected version of Stage 3.

In looking at Stage 4, I noticed that the moves allowed in that stage all perform an even permutation on the edges. Thus, if after completing stage 3, if the edges were in an odd permutation state, they would have to remain in an odd permutation state in stage 4 (as well as stage 5). Since the edge permutation of the solved cube is trivially an even permutation, it is apparent that Stage 3 must leave the edges in an even permutation. As a result, it is necessary to add additional state information for the analysis of Stage 3. That information is whether the edges are in an even permutation or an odd permutation. It is easy to incorporate this new information into the analysis. A separate boolean is added to track whether the edge permutation is odd or even. The moves f, f', b, and b' change the state of the boolean, while all other Stage 3 moves (U, U', U2, u2, D, D', D2, d2, L2, l2, R2, r2, F2, f2, B2, b2) leave the boolean unchanged.

The main problem is that the number of total states doubles to 23,189,166,000. The symmetry-reduced coordinate space I used doubles to 3,176,573,400 values, and the actual number of unique positions with respect to applicable symmetries doubles to 2,898,889,420 positions. I decided to keep using two bits per position in memory, so the main array now consumed nearly 800 MB. So it appears that my program needed to make use of virtual memory to some extent, but the performance did not seem to be degraded too significantly.

4x4x4 Stage 3 analysis

                 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

I have run an analysis for Stage 4 of my five 5-stage analysis. While I plan to do some additional validation checking of the results before giving details, the analysis indicated it takes 16 slice turns (maximum) to do this stage.

Assuming the correctness of this and the earlier results, this 5-stage analysis indicates that the 4x4x4 cube can be solved for any legally scrambled configuration in no more than 78 slice turns! (11 + 18 + 14 + 16 + 19 = 78)

I have tried doing internet searches for any information on an upper bound for the number of moves to solve the 4x4x4, but haven't been able to find any mention of other upper bound values. If anyone knows of any, I would like to know. But I am guessing that no upper bound lower than this value has been determined to this date.

In doing my validation work for my 5-stage analysis, I found that I made a mistake in the handling of the corner configurations in my stage 4 analysis. It now looks to me that my stage 4 requires 17 slice turns maximum, not 16. So with this correction, the total number of slice turns possibly required is now 79.

On the positive side, I have been creating a solver program that will take a 4x4x4 position, and directly solve it using the results of the 5-stage analysis. I have used it to take a test case through the first four stages, and it generated a correct move sequence to transform the initial position into a squares coset position. So now I need to add stage 5 to my solver, and try a lot more test cases.

It looked to me that there might be a problem with my stage 5 results, so I've concentrated on testing the first four stages, and now will look at the fifth stage. It is currently my belief that 19 is still the maximum number of slice turns needed for stage 5.

Well, certainly 7,401,196,841,564,901,869,874,093,974,498,574,335,999,999,999 was known to be an upper bound. But my value of 78 may be the first "reasonably close" upper bound to be claimed.

I might mention that Stage 3 in my analysis has just two antipodes (and they are symmetrically equivalent), so this might allow reducing the upper bound to 77.

In the old "cube-lovers" archives, Dan Hoey had calculated lower bounds of 41 quarter-turn twist moves, and 37 quarter turns of slices ("slabs" in his terminology). He also gave 48 as a lower bound for the 4x4x4 supercube in quarter-turn twist moves. Hoey used counting arguments to arrive at his numbers. I am assuming that we don't have any "known" positions of that depth.

In a quick search, I did not find any lower bounds for any half-turn metrics.