Home »

Solving the 4x4x4 in 68 turns

Submitted by Bruce Norskog on Wed, 02/14/2007 - 01:03.

I have completed a five-stage analysis of the 4x4x4 cube showing that it can always be solved using at most 68 turns. The analysis used the same five stages that were used in my prior posts where I claimed the 4x4x4 cube can be solved in 79 single-slice turns, or alternatively in 85 twists. The difference in this analysis is that it allows any single layer turn or double layer turn (where the two layers are any two adjacent layers and moved together) to be counted as a "turn." In some prior posts, I referred to these turns as "block turns." So the set of turns about the U-D axis that count as one turn are the following:
  U,U',U2,u,u',u2,(Uu),(Uu)',(Uu)2,
  D,D',D2,d,d',d2,(Dd),(Dd)',(Dd)2,
  (ud'),(u'd),(ud')2

Similar turns for the other two axes are counted as single turns.

For more information about the five stages used in the analysis, see my post titled "The 4x4x4 can be solved in 79 moves (STM)." Note each stage further restricts the moves allowed in the previous stage, so that what's achieved in one stage is not lost when doing the following stages. Below I list the moves allowed in each stage.

Stage 1
Turns allowed:
  U,U',U2,u,u',u2,(Uu),(Uu)',(Uu)2,
  D,D',D2,d,d',d2,(Dd),(Dd)',(Dd)2,
  (ud'),(u'd),(ud')2,
  L,L',L2,l,l',l2,(Ll),(Ll)',(Ll)2,
  R,R',R2,r,r',r2,(Rr),(Rr)',(Rr)2,
  (lr'),(l'r),(lr')2,
  F,F',F2,f,f',f2,(Ff),(Ff)',(Ff)2,
  B,B',B2,b,b',b2,(Bb),(Bb)',(Bb)2,
  (fb'),(f'b),(fb')2
One-time whole cube rotations allowed:
  120-degree turns (either direction) about the UFL-DBR axis.

Stage 2
Turns allowed:
  U,U',U2,u,u',u2,(Uu),(Uu)',(Uu)2,
  D,D',D2,d,d',d2,(Dd),(Dd)',(Dd)2,
  (ud'),(u'd),(ud')2,
  L2,l2,(Ll)2, R2,r2,(Rr)2,(lr')2,
  F2,f,f',f2,(Ff)2,
  B2,b,b',b2,(Bb)2,
  (fb'),(f'b),(fb')2
One-time whole cube rotations allowed:
  90-degree turn about U-D axis.

Stage 3
Turns allowed:
  U,U',U2,u2,(Uu)2,
  D,D',D2,d2,(Dd)2,(ud')2,
  L2,l2,(Ll)2, R2,r2,(Rr)2,(lr')2,
  F2,f,f',f2,(Ff)2,
  B2,b,b',b2,(Bb)2,
  (fb'),(f'b),(fb')2

Stage 4
Turns allowed:
  U,U',U2,u2,(Uu)2,
  D,D',D2,d2,(Dd)2,(ud')2,
  L2,l2,(Ll)2, R2,r2,(Rr)2,(lr')2,
  F2,f2,(Ff)2, B2,b2,(Bb)2,(fb')2

Stage 5
Turns allowed:
  U2,u2,(Uu)2, D2,d2,(Dd)2,(ud')2,
  L2,l2,(Ll)2, R2,r2,(Rr)2,(lr')2,
  F2,f2,(Ff)2, B2,b2,(Bb)2,(fb')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 are 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             216               23
   3           5,250              371
   4         111,444            7,112
   5       2,118,252          132,814
   6      32,552,448        2,036,017
   7     311,018,796       19,443,181
   8     945,744,666       59,115,320
   9     315,640,704       19,729,932
  10       1,283,292           80,238
       -------------      -----------
       1,608,475,077      100,545,012

Stage 2

distance   positions           unique
  0               24               14
  1               60               18
  2            1,098              181
  3           14,208            1,967
  4          188,848           24,341
  5        2,399,042          302,848
  6       28,103,592        3,521,470
  7      258,338,328       32,306,960
  8    1,473,529,948      184,206,032
  9    3,777,447,012      472,207,437
 10    4,797,332,868      599,732,284
 11    5,575,443,832      697,000,697
 12    4,467,302,876      558,453,138
 13    1,227,407,340      153,439,494
 14       15,338,004        1,917,889
 15              320               40
       -------------      -----------
      21,622,847,400    2,703,114,810

Stage 3

distance   positions           unique
  0               12                7
  1               36               13
  2              408               69
  3            4,812              683
  4           60,232            7,856
  5          731,762           92,591
  6        8,464,192        1,061,773
  7       94,683,646       11,847,569
  8      961,683,356      120,247,564
  9    6,888,947,908      861,200,907
 10   13,895,117,674    1,736,980,616
 11    1,339,418,678      167,443,068
 12           53,284            6,704
      --------------    -------------
      23,189,166,000    2,898,889,420
 

Stage 4

distance   positions           unique
  0               12                5
  1               24                4
  2              300               30
  3            1,880              153
  4           13,392              957
  5           88,116            5,927
  6          579,480           37,395
  7        3,758,368          238,109
  8       23,165,960        1,457,522
  9      120,312,432        7,545,330
 10      443,708,576       27,781,764
 11      822,628,996       51,488,958
 12      804,166,096       50,341,287
 13      349,446,264       21,886,551
 14       25,199,768        1,586,273
 15           10,336              867
       -------------      -----------
       2,593,080,000      162,371,132

Stage 5

distance    positions          unique
   0                4               2
   1               72              11
   2              864              50
   3            9,700             403
   4          101,060           3,267
   5          939,956          25,028
   6        7,748,796         182,815
   7       56,687,544       1,252,926
   8      362,251,572       7,775,843
   9    1,975,717,680      41,920,351
  10    8,792,371,296     185,298,651
  11   28,896,905,328     606,099,406
  12   56,844,273,080   1,190,199,719
  13   43,883,159,504     921,188,861
  14    5,918,564,320     125,844,537
  15       28,351,768         672,920
  16            3,024             242
      ---------------   -------------
      146,767,085,568   3,080,465,032

The number of turns required (worst case) for each stage are 10, 15, 12, 15, and 16, respectively. Thus, any position of the 4x4x4 can be solved using no more than 68 turns, with the meaning of "turns" as defined above.

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

It's good to see this develop

Submitted by Mike G on Wed, 02/21/2007 - 12:03.
It's good to see this development! A lot of work has gone into it.

It would be nice to see this algorithm in action, without having to calculate the huge tables for each phase. Have you considered making a solver that uses IDA* (with relatively small pruning tables) for each of the 5 stages separately?
» login or register to post comments

Re: It's good to see this develop

Submitted by Bruce Norskog on Thu, 02/22/2007 - 00:35.
> It would be nice to see this algorithm in action, without
> having to calculate the huge tables for each phase.
> Have you considered making a solver that uses IDA*
> (with relatively small pruning tables) for each of
> the 5 stages separately?

I have thought about this, but so far I haven't worked on implementing an IDA* solver for these stages. I will first be updating my solver so that it will allow a choice of metrics at runtime, as long as the corresponding (very large) data files are available. Unfortunately, the large sizes of these files causes problems with distribution, and it will take some effort to fix up the program to allow these files to be easily generated by users automatically.

So using IDA* with relatively small pruning tables as you mentioned would be a reasonable way to provide a solver that uses these five stages, and that can easily be distributed. It might also be nice to have the solver try multiple solutions at each stage to find closer to optimal overall solutions. I don't know if I will get to doing this very soon, though.

I'll note that C. W. Tsai has created 7- and 8-step 4x4x4 solvers of the type you mention. His solvers get the centers solved and edges paired up so that the remainder of the solve is done like a 3x3x3, enabling the use of Thistlethwaite's 3x3x3 subgroups for the remaining steps. See http://www.geocities.com/c_w_tsai/solver4/.

» login or register to post comments

Details of 7/8-step solver

Submitted by mrCage on Thu, 09/22/2011 - 02:50.
Hi Bruce!

Do you or any others have the details of Tsai's 7/8 step solver? Even better, does anyone here on this forum have the source code for the solver. I have received questions about it, because i wrote a simple web GUI for it ages ago (8 step version). Now i don't have access to any of it anymore ... Not even my email correspondence with Charles. **sigh**
» login or register to post comments

It appears his solver was on

Submitted by Bruce Norskog on Fri, 09/23/2011 - 22:20.

It appears his solver was on geocities.com which was discontinued a couple of years ago. Unfortunately, I don't recall exactly what the first three phases did. There are some clues about this in the thread on the Yahoo speedsolvingrubikscube group. The 4th phase, of course, brought the cube to a 3x3x3 reduction state (without parity conditions I presume) after which the four Thistlethwaite phases were used to finish the solve. The 7-step version combined two of the steps.

» login or register to post comments

Tsai's 4x4x4 algorithm

Submitted by stannic on Sat, 09/24/2011 - 06:29.

I've downloaded Tsai's solvers some time ago. There was no source code available, but two compiled Windows executables and readme file. There was also HTML pages with detailed description of all stages. I have these pages in RTF format; unfortunately I don't know how to attach files on this forum. Below is short description for anyone interested. Maybe it is possible to contact Charles Tsai for source code or better description.

7-step version of the algorithm goes through the following chain:

Step  Permitted moves
   1. < R,L,F,B,U,D,r,l,f,b,u,d >
   2. < R,L,F,B,U,D,r,l,f2,b2,u2,d2 >
   3. < R2,L2,F,B,U,D,r2,l2,f2,b2,u2,d2 >
   4. < R2,L2,F2,B2,U,D,r2,l2,f2,b2 >
   5. < R2,L2,F,B,U,D >
   6. < R2,L2,F2,B2,U,D >
   7. < R2,L2,F2,B2,U2,D2 >

1st step objective is to place R and L centers on the R and L faces.

In 2nd stage, we should:
1. Orient edges (separate low and high edges).
2. Put F and B centers onto F and B faces; put U and D centers onto U and D faces.
3. Put R and L centers into one of 12 positions that can be solved in later steps.
4. Make the low-edge and high-edge permutation parities match.

In 3rd stage, we should:
1. Match 4 pairs of edges and place them at BR, BL, FL, and FR.
2. Put R and L centers in columns.
3. Put F and B centers in columns.

In 4th stage, we need to:
1. Pair up the remaining edges.
2. Solve the centers.
3. Match the edges and corners permutation parities.

5th, 6th and 7th steps are Thistlethwaite's 2nd, 3rd and 4th.

8-step algorithm uses the following moves in each of steps:

Step  Permitted moves
   1. < R,L,F,B,U,D,r,l,f,b,u,d >
   2. < R,L,F,B,U,D,r,l,f2,b2,u2,d2 >
   3. < R2,L2,F,B,U,D,r2,l2,f2,b2,u2,d2 >
   4. < R2,L2,F2,B2,U,D,r2,l2,f2,b2 >
   5. < R,L,F,B,U,D >
   6. < R2,L2,F,B,U,D >
   7. < R2,L2,F2,B2,U,D >
   8. < R2,L2,F2,B2,U2,D2 >

1st stage is the same as in 7-step version.

2nd stage objectives are:
1. Orient corresponding low and high edges the same way. Make sure that the number of misoriented edges is a multiple of 4. (Instead of requiring that all edges are oriented correctly, we require only that a low edge and its corresponding high edge be oriented the same way: both correctly or both incorrectly.)
2. Put F and B centers onto F and B faces; put U and D centers onto U and D faces.
3. Put R and L centers into one of 12 positions that can be solved in later steps.
4. Make the low-edge and high-edge permutation parities match.

3rd and 4th stages objectives are the same as in 7-step version.

5th stage is Thistlethwaite's 1st (objective is to orient edge pairs). In 7-step version, this was done in step 2.

6th-8th stages are Thistlethwaite's 2nd-4th.

- stannic

Edit: here is the archive with Charles Tsai's binaries and descriptions from dead geocities.com.

» login or register to post comments