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

God's algorithm for 4x4x4 Squares Set

I have computed God's algorithm for the set of Rubik's Revenge (4x4x4 cube) positions that are reachable by the following set of moves: { U^2, u^2, d^2, D^2, L^2, l^2, r^2, R^2, F^2, f^2, b^2, B^2 }. Actually, not all of the above moves need to be included in order to generate the whole set. Since these moves are expressed as squares of other basic moves in the group theory notation, the set of positions reachable by these moves is referred to as the Squares Group. In my analysis thus far, I have considered the four centers of a given face to be indistinguishable. That is, I am considering only the "plain" 4x4x4, not the 4x4x4 supercube (where all centers are taken to be distinguishable from the others). With this simplification, this set of positions does not actually form a mathematical group, so I will refer to it as the Squares Set here. 19 slice turns was found to be sufficient to solve any of the positions in this set.

I have also used two other metrics: "twist turns" and "block turns." Twist turns I consider to be moves involving movement along a single cut: { R^2, D^2, L^2, R^2, F^2, B^2, (U u)^2, (D d)^2, (L l)^2, (R r)^2, (F f)^2, (B b)^2 }. Block turns I consider to be any move that moves a 4x4x1 or 4x4x2 block with respect to the rest of the cube. This consists of the set of slice turns, the set of twist turns, plus { (u d')^2, (l r')^2, (f b')^2 }. (I include only half-turn moves for the various metrics in the present discussion, as I am here considering only moves that keep the puzzle within the Squares Set.)

The summary of the results is given below.

```Squares Set of 4x4x4 cube, Slice turns

distance    positions   reduced count   unique wrt M
0                4               2              2
1               48               6              6
2              420              25             23
3            3,456             146            124
4           27,168             974            806
5          203,752           5,939          5,197
6        1,451,996          40,034         33,853
7        9,527,856         251,254        211,333
8       56,528,036       1,470,957      1,223,997
9      295,097,696       7,549,296      6,305,655
10    1,306,291,304      32,966,074     27,704,719
11    4,761,203,264     118,977,923    100,510,701
12   13,820,728,272     341,838,162    290,661,124
13   29,956,341,744     735,369,920    628,414,595
14   43,427,866,752   1,065,516,952    910,241,690
15   36,297,535,208     899,375,088    761,210,397
16   14,711,566,720     373,368,740    309,104,278
17    2,063,584,704      55,606,300     43,573,552
18       59,082,112       1,935,232      1,262,024
19           45,056           1,280            956
---------------   -------------  -------------
146,767,085,568   3,634,274,304  3,080,465,032

Squares Set of 4x4x4 cube, Twist turns, Block turns

Twist Turns                       Block Turns

distance    positions    unique wrt M         positions    unique wrt M
0                4               2                 4               2
1               36               5                72              11
2              252              15               864              50
3            1,728              70             9,700             403
4           11,528             374           101,060           3,267
5           72,300           1,988           939,956          25,028
6          431,188          10,423         7,748,796         182,815
7        2,459,832          55,600        56,687,544       1,252,926
8       13,361,660         291,127       362,251,572       7,775,843
9       68,407,980       1,464,351     1,975,717,680      41,920,351
10      326,021,992       6,914,502     8,792,371,296     185,298,651
11    1,414,642,236      29,844,904    28,896,905,328     606,099,406
12    5,361,506,980     112,742,406    56,844,273,080   1,190,199,719
13   16,520,565,624     346,616,171    43,883,159,504     921,188,861
14   36,467,453,404     764,073,198     5,918,564,320     125,844,537
15   47,828,766,672   1,002,434,703        28,351,768         672,920
16   30,852,487,408     648,178,826             3,024             242
17    7,546,175,832     159,746,983                 0               0
18      362,229,856       8,020,105                 0               0
19        2,450,544          67,417                 0               0
20           38,512           1,862                 0               0
---------------   -------------   ---------------   -------------
146,767,085,568   3,080,465,032   146,767,085,568   3,080,465,032

```

My program counted positions differing by the orientation of the whole cube as distinct positions, but only 180-degree whole cube rotations were considered. This results in four "solved" positions, the identity position where every facelet is on the "correct" face of the cube, and three positions obtained by rotating the identity position 180 degrees with respect to the three axes. Simply divide the numbers in the "positions" column by four to get the effective number of distinct positions when positions differing only by these whole cube rotations are considered to be the same.

My program used a sym-coordinate for the edge configuration of 21908 positions * 48 symmetries. So the number of "symmetry-reduced" positions was 21908*96*12^3 = 3634274304. Using two-bits per element, the main array was 908,568,576 bytes. Note, since the four centers of a given face are considered indistinguishable, the inverse of a position is ambiguous. Because of this, I believe you can't use antisymmetry to further reduce the positions.

The true number of positions when using symmetry with respect to all cubies, was found to be 3,080,465,032. I haven't performed a theoretical calculation to verify this number.

## Comment viewing options

### Nice work. I am just in awe

Nice work.
I am just in awe of the incredible stuff that has been done here in the last 6 months by you, Silviu, Tomas, Jerry and others.

> this set of positions does not actually form a mathematical group,
> so I will refer to it as the Squares Set here.

I think it is usually called a coset space. Let H be the group of permutations that invisibly permute the centres of a solved 4x4x4 (isomorphic to S4^6). Let g be any cube permutation. The result of applying g on the solved cube will look just the same if we apply some permutation in H first. Therefore Hg is the set of all permutations that look the same as g when applied to a solved cube.

Every position on the 4x4x4 cube is really a coset Hg for some g, and moves/permutations act on this by further right-multiplication. This is why is is a coset space.

Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles/

### Plan for 5-stage 4x4x4 analysis

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.

### Stage 1 results

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

### Bad results for stage 1

Sorry, I have determined my results shown for stage 1 are in fact quite incorrect. The move table for corner orientation in my program was being generated incorrectly. I'll try to have corrected results in another day or two.

### stage 1 results

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

### stage 1 using quarter-turns

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

### Stage 2 results (slice turns)

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:

U, U', U2, u, u', u2, D, D', D2, d, d', d2,
L2, l2, R2, r2,
F2, f, f', f2, B2, b, b', b2
```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
```

### Stage 3 results

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

### Stage 3 Correction

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

### Stage 4 analysis run

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.

### Oops, make that 79 instead

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.

### Congratulations Bruce! I

Congratulations Bruce!

I think this is the first upper bound on the 4x4x4 cube. I am surprised of how low this number is (no particular reason why).

Btw, do you know any lower bounds for the 4x4x4?

Silviu

### some former 4x4x4 bounds

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.

### 4x4x4 lower bound

At most 36^29 + 36^28 + 36^27 + ... (approx. 1/6 of the number of positions of a 4x4) positions can be reached in 29 slice turns or less, so there are positions that require at least 30 slice turns.