Home »

Number of 4x4x4 positions for up to 5 moves

Submitted by Bruce Norskog on Sun, 07/10/2011 - 20:35.

After hearing about this paper which talks about the size of God's number for nxnxn cubes, I was thinking about what we currently know about God's algorithm for the 4x4x4 and realized that I couldn't seem to find any partial distance distributions on the 4x4x4 on the web.

So I've run my own analyses to get the number of positions up to 5 moves from the solved state. I have done this for six metrics. First, I have "single-slice" metrics where a move is only allowed to turn a single layer. Second, I have twist metrics where a move is only allowed to twist the cube along one plane. This is sometimes called face-turn metric because a face layer (possibly along with additional adjacent layers) is (are) turned with respect to the rest of the cube. Finally I also used what I termed "block turns" where some block of one or more adjacent layers (not necessarily including a face layer) are turned with respect to the rest of the cube. For each of these, I also considered whether or not a move must be restricted to quarter-turns only.

The tables give the number of positions at each distance from solved, as well as the cumulative number of positions up to the given distance. The tables also include the branching factor (b.f.) or the ratio of the number of positions at one distance with that of the previous distance. Of course, this is for a 4x4x4 where the four center pieces for each face are considered indistinguishable. Also, the orientation of the puzzle is considered not to matter. (I used moves that kept a particular corner piece fixed to ensure I didn't count positions more than once.) My numbers only go up to 5 moves, but it's a start.

single-slice turns (half-turns allowed)

moves  positions     b.f.  cumulative pos.
  0            1                      1
  1           36   36                37
  2          999   27.75           1036
  3        27186   27.2132        28222
  4       738096   27.1499       766318
  5     20000066   27.0968     20766384


single-slice turns (only quarter-turns allowed)

moves  positions     b.f.  cumulative pos.
  0            1                      1
  1	      24   24                25
  2          450   18.75            475
  3         8328   18.5067         8803
  4       154035   18.4960       162838
  5      2846464   18.4793      3009302


twists (half-turns allowed)

moves  positions     b.f.  cumulative pos.
  0            1                      1
  1           27   27                28
  2          567   21               595
  3        11742   20.7090        12337
  4       243152   20.7079       255489
  5      5026667   20.6729      5282156


twists (only quarter-turns allowed)

moves  positions     b.f.  cumulative pos.
  0            1                      1
  1           18   18                19
  2          261   14.5             280
  3         3732   14.2989         4012
  4        53379   14.3031        57391
  5       763386   14.3012       820777


block turns (half-turns allowed)

moves  positions     b.f.  cumulative pos.
  0            1                      1
  1           54   54                55
  2         2070   38.3333         2125
  3        78649   37.9947        80774
  4      2973289   37.8045      3054063
  5    111963451   37.6564    115017514


block turns (only quarter-turns allowed)
		
moves  positions     b.f.  cumulative pos.
  0            1                      1
  1           36   36                37
  2          972   27              1009
  3        25962   26.7099        26971
  4       693356   26.7066       720327
  5     18497026   26.6775     19217353

Finally, I note that it's now been 5 years since I announced that 79 moves suffice.

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

(Comment is withdrawn)

Submitted by stannic on Thu, 08/18/2011 - 20:58.
(Comment is withdrawn)
» login or register to post comments

Nice work

Submitted by rokicki on Thu, 07/14/2011 - 11:45.
I wanted to mention that I am happy for these results, glad that we've got some momentum going on the 4x4x4!

-tom
» login or register to post comments

some deeper results

Submitted by Bruce Norskog on Thu, 07/14/2011 - 23:18.

I've added symmetry reduction to my program, so I now have some deeper results.

single-slice turns (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           36          37           4              5
  2          999        1036          36             41
  3        27186       28222         619            660
  4       738096      766318       15771          16431
  5     20000066    20766384      418952         435383
  6    541569809   562336193    11297967       11733350


single-slice turns (only quarter-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1	      24          25           2              3
  2          450         475          17             20
  3         8328        8803         194            214
  4       154035      162838        3303           3517
  5      2846464     3009302       59732          63249
  6     52574466    55583768     1097600        1160849


twists (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           27          28           4              5
  2          567         595          29             34
  3        11742       12337         334            368
  4       243152      255489        5624           5992
  5      5026667     5282156      108448         114440
  6    103810159   109092315     2186949        2301389


twists (only quarter-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           18          19           2              3
  2          261         280          14             17
  3         3732        4012         102            119
  4        53379       57391        1209           1328
  5       763386      820777       16307          17635
  6     10915544    11736321      229205         246840
  7    156053230   167789551     3258621        3505461


block turns (only quarter-turns allowed)
		
moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           36          37           4              5
  2          972        1009          38             43
  3        25962       26971         609            652
  4       693356      720327       14848          15500
  5     18497026    19217353      388011         403511
  6    493391567   512608920    10295551       10699062
» login or register to post comments

more results

Submitted by Bruce Norskog on Fri, 07/15/2011 - 21:53.
I now have some more updated tables. 
single-slice turns (only quarter-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1	      24          25           2              3
  2          450         475          17             20
  3         8328        8803         194            214
  4       154035      162838        3303           3517
  5      2846464     3009302       59732          63249
  6     52574466    55583768     1097600        1160849
  7    970712112  1026295880    20234569       21395418	
  

twists (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           27          28           4              5
  2          567         595          29             34
  3        11742       12337         334            368
  4       243152      255489        5624           5992
  5      5026667     5282156      108448         114440
  6    103810159   109092315     2186949        2301389
  7   2143281226  2252373541    44810199       47111588	


twists (only quarter-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           18          19           2              3
  2          261         280          14             17
  3         3732        4012         102            119
  4        53379       57391        1209           1328
  5       763386      820777       16307          17635
  6     10915544    11736321      229205         246840
  7    156053230   167789551     3258621        3505461
  

block turns (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1              1            1           1
  1           54             55            8           9
  2         2070           2125           87          96
  3        78649          80774         2052        2148
  4      2973289        3054063        66299       68447
  5    111963451      115017514      2376654     2445101
  6   4212573974     4327591488     88205742    90650843
» login or register to post comments

another update

Submitted by Bruce Norskog on Wed, 07/20/2011 - 08:01.

I've updated the single-slice metric table in the above post to include positions at a distance of 8. This is wrong. What I calculated was single-slice metric (with half-turns allowed) at a distance of 7. There were 305,559,127 symmetry-reduced positions or a total of 14,661,687,334 positions at that distance. I am wondering if Mark could remove the distance 8 line of the first table of the previous post. Thanks.

The correct table for single-slice turns with half-turns allowed is given below.

single-slice turns (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           36          37           4              5
  2          999        1036          36             41
  3        27186       28222         619            660
  4       738096      766318       15771          16431
  5     20000066    20766384      418952         435383
  6    541569809   562336193    11297967       11733350
  7  14661687334 15224023527   305559127      317292477

I'm reaching the limit of what's practical to do with my current hash-table based breadth-first search program. I'm looking at seeing if I can create a program more like what Jerry Bryan used to generate distance distributions for the 3x3x3. This will include handling the symmetry reduction much more efficiently than my current program.

» login or register to post comments

I have made some improvements

Submitted by Bruce Norskog on Sun, 07/31/2011 - 11:50.

I have made some improvements to my program, and now have results for one move farther out in four of the metrics.

single-slice turns (only quarter-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           24          25           2              3
  2          450         475          17             20
  3         8328        8803         194            214
  4       154035      162838        3303           3517
  5      2846464     3009302       59732          63249
  6     52574466    55583768     1097600        1160849
  7    970712112  1026295880    20234569       21395418
  8  17918833564 18945129444   373366693      394762111


twists (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           27          28           4              5
  2          567         595          29             34
  3        11742       12337         334            368
  4       243152      255489        5624           5992
  5      5026667     5282156      108448         114440
  6    103810159   109092315     2186949        2301389
  7   2143281226  2252373541    44810199       47111588
  8  44246249410 46498622951   922837620      969949208


twists (only quarter-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           18          19           2              3
  2          261         280          14             17
  3         3732        4012         102            119
  4        53379       57391        1209           1328
  5       763386      820777       16307          17635
  6     10915544    11736321      229205         246840
  7    156053230   167789551     3258621        3505461
  8   2230797130  2398586681    46507778       50013239
  9  31888201684 34286788365   664478297      714491536


block turns (only quarter-turns allowed)
		
moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1           1           1              1
  1           36          37           4              5
  2          972        1009          38             43
  3        25962       26971         609            652
  4       693356      720327       14848          15500
  5     18497026    19217353      388011         403511
  6    493391567   512608920    10295551       10699062
  7  13159327676 13671936596   274257403      284956465
» login or register to post comments

results for 7 block turns

Submitted by Bruce Norskog on Sun, 08/07/2011 - 00:15.

I have now completed tabulating the number of positions of the 4x4x4 out to a distance of 7 block turns. As my hash table is limited to around 50 million entries, I partitioned the cube positions into 130 sets based upon the 77802 possible (symmetry-reduced) corner configurations and the positions of 3 edge cubies.

block turns (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1              1            1           1
  1           54             55            8           9
  2         2070           2125           87          96
  3        78649          80774         2052        2148
  4      2973289        3054063        66299       68447
  5    111963451      115017514      2376654     2445101
  6   4212573974     4327591488     88205742    90650843
  7 158458718464   162786309952   3305688035  3396338878
» login or register to post comments

4x4x4 supercube up to 7 block turns

Submitted by Bruce Norskog on Thu, 08/18/2011 - 01:00.

I have now computed the number of 4x4x4 supercube (where all center pieces are considered distinguishable) positions up to 7 block turns.

block turns (half-turns allowed) - 4x4x4 supercube

moves  positions     cumulative    positions  cumulative pos.
                      positions      mod M         mod M

  0            1              1            1           1
  1           54             55            8           9
  2         2070           2125           87          96
  3        78832          80957         2058        2154
  4      2991581        3072538        66783       68937
  5    113130559      116203097      2403155     2472092
  6    273801288     4390004385     89514868    91986960
  7 161363025509   165753029894   3366631574  3458618534
» login or register to post comments