Home »

Solving the 4x4x4 in 85 twists

Submitted by Bruce Norskog on Wed, 11/29/2006 - 00:45.

In my posting titled "The 4x4x4 can be solved in 79 moves (STM)," I reported about an analysis I did where the 4x4x4 cube is solved in five stages. In that analysis, a move was considered to be any quarter-turn or half-turn of a single slice.

I have now completed a similar analysis of the 4x4x4 cube where a move is considered to be any quarter- or half-turn twist of the cube, and where a twist is considered to be one portion of the cube (a face layer, or a block consisting of a face layer and the adjacent inner layer) being turned with respect to the rest of the cube. The analysis indicates that any valid position of the 4x4x4 cube can be solved via these five stages using no more than 85 twists.

See the other article for more details about the five stages. Here, I'll simply list the various moves allowed to be used in each stage.

Stage 1
Twists allowed:
  U,U',U2,(Uu),(Uu)',(Uu)2, D,D',D2,(Dd),(Dd)',(Dd)2,
  L,L',L2,(Ll),(Ll)',(Ll)2, R,R',R2,(Rr),(Rr)',(Rr)2,
  F,F',F2,(Ff),(Ff)',(Ff)2, B,B',B2,(Bb),(Bb)',(Bb)2
One-time whole cube rotations allowed:
  120-degree turns (either direction) about the UFL-DBR axis.

Stage 2
Twists allowed:
  U,U',U2,(Uu),(Uu)',(Uu)2, D,D',D2,(Dd),(Dd)',(Dd)2,
  L2,(Ll)2, R2,(Rr)2,
  F2,(Ff)2, B2,(Bb)2
Inner slice turns allowed (counted as two twists):
  f,f',b,b'
One-time whole cube rotations allowed:
  90-degree turn about U-D axis.
Note that this stage allows inner slice turns in order for it to be possible to solve all positions of this stage while also not allowing any invalid positions for this stage to be reachable. But since inner slice turns require twisting the cube in two places, these turns are counted as two twists.

Stage 3
Twists allowed:
  U,U',U2,(Uu)2, D,D',D2,(Dd)2,
  L2,(Ll)2, R2,(Rr)2,
  F2,(Ff)2, B2,(Bb)2
Inner slice turns allowed (counted as two twists):
  f,f',b,b'
This stage allows the same inner slice turns as allowed in stage 2. Note that these four inner slice turns are the only turns allowed in this stage that are not allowed in the next stage. That means that one of these moves is always the last move of this stage. But since these moves are always counted as 2 twists, this stage has no positions of distance 1.

Stage 4
Twists allowed:
  U,U',U2,(Uu)2, D,D',D2,(Dd)2,
  L2,(Ll)2, R2,(Rr)2,
  F2,(Ff)2, B2,(Bb)2

Stage 5
Twists allowed:
  U2,(Uu)2, D2,(Dd)2,
  L2,(Ll)2, R2,(Rr)2,
  F2,(Ff)2, B2,(Bb)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 is 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             108               11
   3           1,932              136
   4          31,218            2,000
   5         463,422           29,136
   6       6,029,550          377,432
   7      62,063,820        3,880,774
   8     383,382,798       23,965,573
   9     849,606,252       53,106,043
  10     303,401,406       18,965,318
  11       3,494,562          218,585
       -------------      -----------
       1,608,475,077      100,545,012

Stage 2

distance   positions           unique
  0               24               14
  1               24                6
  2              168               30
  3            1,200              185
  4            8,140            1,129
  5           56,178            7,341
  6          367,100           46,777
  7        2,302,670          289,977
  8       14,124,912        1,770,189
  9       81,750,306       10,228,545
 10      417,018,176       52,143,753
 11    1,634,702,952      204,363,892
 12    3,979,487,116      497,483,783
 13    5,732,083,942      716,574,370
 14    5,573,127,792      696,690,156
 15    3,330,770,724      416,371,475
 16      815,661,700      101,967,538
 17       40,568,480        5,073,399
 18          813,084          101,862
 19            2,712              389
       -------------      -----------
      21,622,847,400    2,703,114,810

Stage 3

distance   positions           unique
  0                12               7
  1                 0               0
  2                24               6
  3               240              37
  4             1,628             249
  5            12,432           1,659
  6            84,596          10,884
  7           516,020          65,214
  8         2,904,664         364,740
  9        15,341,866       1,921,737
 10        81,949,156      10,251,916
 11       461,971,534      57,764,972
 12     2,221,037,592     277,666,652
 13     6,858,548,392     857,379,146
 14     8,906,738,640   1,113,405,703
 15     4,086,085,086     510,797,506
 16       532,101,222      66,522,880
 17        21,780,108       2,724,445
 18            92,746          11,656
 19                42              11
       --------------   -------------
       23,189,166,000   2,898,889,420

Stage 4

distance    positions          unique
  0                12               5
  1                24               4
  2               156              18
  3               816              67
  4             4,336             309
  5            24,776           1,690
  6           132,432           8,747
  7           670,284          43,041
  8         3,382,304         214,202
  9        16,909,008       1,064,081
 10        76,851,572       4,822,940
 11       285,480,696      17,888,097
 12       738,430,708      46,230,114
 13       984,159,264      61,595,705
 14       454,803,540      28,476,121
 15        32,176,504       2,022,258
 16            53,568           3,733
        -------------     -----------
        2,593,080,000     162,371,132   

Stage 5

distance    positions          unique
   0                4               2
   1               36               5
   2              252              15
   3            1,728              70
   4           11,528             374
   5           72,300           1,988
   6          431,188          10,423
   7        2,459,832          55,600
   8       13,361,660         291,127
   9       68,407,980       1,464,351
  10      326,021,992       6,914,502
  11    1,414,642,236      29,844,904
  12    5,361,506,980     112,742,406
  13   16,520,565,624     346,616,171
  14   36,467,453,404     764,073,198
  15   47,828,766,672   1,002,434,703
  16   30,852,487,408     648,178,826
  17    7,546,175,832     159,746,983
  18      362,229,856       8,020,105
  19        2,450,544          67,417
  20           38,512           1,862
      ---------------   -------------
      146,767,085,568   3,080,465,032

The number of twists required (worst case) for each stage are 11, 19, 19, 16, and 20, respectively. Thus, any position of the 4x4x4 can be solved using no more than 85 twists.

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

Make that 83 twists

Submitted by Bruce Norskog on Tue, 02/27/2007 - 23:38.

During the process of trying out the 85-twist, five-stage procedure for solving the 4x4x4, I noticed that the generated solutions for random scrambles contained twist sequences that could obviously be optimized. While this was to be expected across stage boundaries, there were such sequences that were not across a stage boundary. These were three-twist sequences that could be shortened to two twists. For example, F2 and f are allowable single-slice turns for stages 2 and 3. The combination (F2 f) could be achieved by substituting (Ff) F' for f, so (F2 f) could be done as three twists, F2 (Ff) F'. Of course, the same can be done with only two twists, (Ff) F.

Thus, I have now done a new calculation for stages 2 and 3 that allow the following double-twist moves along with the other moves allowed before:
  (Ff) F = F2 f
  (Ff)' F' = F2 f'
  (Bb) B = B2 b
  (Bb)' B' = B2 b'

Of course, these double-twists count as 2 twists.

The result of these analyses reduces the maximum number of twists for these stages from 19 to 18 for each stage. This reduces the upper bound to solve the 4x4x4 from 85 to 83. The summary for these analyses is given below.

Stage 2

distance   positions           unique
  0               24               14
  1               24                6
  2              168               30
  3            1,296              197
  4            9,564            1,307
  5           70,402            9,136
  6          495,508           62,895
  7        3,369,218          423,478
  8       22,165,448        2,775,775
  9      136,299,902       17,047,938
 10      711,992,120       89,016,697
 11    2,580,017,520      322,533,475
 12    5,239,924,216      655,047,340
 13    6,401,953,318      800,311,196
 14    4,936,417,944      617,095,579
 15    1,489,502,272      186,205,974
 16       99,551,228       12,448,635
 17        1,074,172          134,686
 18            3,056              452
       -------------      -----------
      21,622,847,400    2,703,114,810

Stage 3

distance   positions           unique
  0               12                7
  1                0                0
  2               24                6
  3              240               37
  4            1,628              249
  5           12,816            1,707
  6           91,220           11,712
  7          588,372           74,258
  8        3,577,144          448,878
  9       20,949,282        2,623,065
 10      123,046,976       15,390,083
 11      715,681,378       89,480,692
 12    3,354,929,964      419,408,897
 13    8,955,143,808    1,119,461,407
 14    7,831,924,984      979,053,519
 15    2,108,992,906      263,651,195
 16       68,139,010        8,521,984
 17        6,085,140          761,574
 18            1,096              150
      --------------    -------------
       23,189,166,000   2,898,889,420
» login or register to post comments