Home »

The 4x4x4 can be solved in 77 single-slice turns

Submitted by Bruce Norskog on Thu, 07/26/2007 - 00:17.

Previously I announced that the 4x4x4 cube could be solved in 79 single-slice turns by solving it in five stages, in a manner similar to the Thistlethwaite 4-stage solution for the 3x3x3. (See The 4x4x4 can be solved in 79 moves (STM).) However, I have now realized my solution to the 2nd stage could have allowed the use of more basic turns than I used. I have realized that:
< U,u,D,d,L2,l2,R2,r2,F2,f,B2,b > = < U,u,D,d,L2,l,R2,r,F2,f,B2,b >
So with l and r replacing generators l2 and r2, you still can not reach any additional positions. As a result, I should have included the moves { l, l', r, r' } along with the other 24 allowed slice turns for that stage.

I have therefore recalculated the solution for Stage 2 using the additional basic moves. This new analysis shows that (in the worst case) two less moves are required than what the previous calculation produced. Therefore, the sum of the worst case values for each of the five stages comes to 77 instead of 79 using the new analysis.

For this new analysis, the distribution of positions at various distances from the solved state for Stage 2 are given below.

Stage 2

                Slice turns
          ------------------------
distance  positions         unique
--------  ---------         ------
  0              24             14
  1              72             17
  2           1,368            194
  3          18,508          2,455
  4         207,996         26,549
  5       2,299,348        290,234
  6      23,858,972      2,991,456
  7     185,459,676     23,195,543
  8     895,556,404    111,954,098
  9   2,495,445,552    311,942,717
 10   3,861,651,288    482,738,888
 11   4,430,801,152    553,917,154
 12   5,214,924,836    651,928,238
 13   3,656,282,908    457,074,674
 14     853,364,112    106,680,277
 15       2,975,072        372,288
 16             112             14
     --------------  -------------
     21,622,847,400  2,703,114,810

I note that my results for what I refer to as "twist turns" and "block turns" may also be improved. I will plan to add follow-ups to this post when I complete those analyses.

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

New upper bounds: 82 twist turns, 67 block turns

Submitted by Bruce Norskog on Mon, 08/13/2007 - 09:15.

I have completed new analyses for "twist turns" and "block turns" for stage 2 of my five stage solution.

The following 2-twist moves were used in the new stage 2 twist turn analysis in addition to the turns used in the previous twist turn analysis for stage 2.
(Ll) L'
(Ll) L
(Ll)' L
(Ll)' L'
(Rr) R'
(Rr) R
(Rr)' R
(Rr)' R'

The following block moves were used in the new stage 2 block turn analysis in addition to the turns used in the previous block turn analysis for stage 2.
l
l'
r
r'
(lr')
(l'r)

With these analyses, the total number of moves that could be required to perform all five stages is now 11+17+18+16+20 = 82 for twist turns, and 10+14+12+15+16 = 67 for block turns. 


                Twist turns                  Block turns
         ------------------------    ----------------------------
distance positions         unique        positions         unique
-------- ---------         ------        ---------         ------
  0             24             14               24             14
  1             24              6               96             31
  2            192             36            2,104            335
  3          1,728            258           31,880          4,334
  4         13,328          1,820          455,264         58,328
  5        102,508         13,262        6,544,244        824,085
  6        751,892         95,316       78,254,108      9,797,869
  7      5,317,152        668,129      592,178,248     74,035,045
  8     36,084,460      4,518,066    2,163,102,392    270,397,194
  9    223,256,252     27,919,844    3,898,385,688    487,327,826
 10  1,091,143,724    136,411,907    4,416,549,980    552,138,877
 11  3,269,334,024    408,698,631    5,377,680,416    672,276,641
 12  5,317,588,388    664,756,768    4,046,752,508    505,880,305
 13  6,027,748,280    753,537,715    1,037,024,016    129,637,853
 14  4,518,494,112    564,851,695        5,886,432        736,073
 15  1,094,478,104    136,822,726
 16     38,480,048      4,811,916
 17         53,160          6,701
    --------------  -------------   --------------  -------------
    21,622,847,400  2,703,114,810   21,622,847,400  2,703,114,810
» login or register to post comments