Lower Bounds for n x n x n Rubik's Cubes (through n=20) in Six Metrics

In January 1981, Dan Hoey posted to cube-lovers a description of a technique to compute a lower bound on God's Number. This technique considered the maximum number of positions that can be reached by what is called "syllables"---consecutive moves on the same axis, possibly turning distinct faces. Since all the moves that make up a syllable commute, we can select a single canonical move sequence to represent every syllable, and then determine how many move sequences of a given total length can be made out of only these syllables. This gives a more accurate bound on God's Number because it eliminates many redundant sequences.

Some time later (and I have been unable to discern exactly when), Richard Carr determined the number of positions for a more general n x n x n Rubik's cube, and Chris Hardwick simplified that formula.

And just recently, Bruce Norskog posted some distance/position count results for the 4x4x4 using six different cube metrics.

I decided to combine all of these ideas, and compute lower bounds for the n x n x n Rubik's cube using all six of Norskog's metrics. The ideas I used were from the above three sources.

I will present the results through $n=20$ below for conciseness. I have results for much much larger cubes, and will present them with a description of the techniques I had to use to make the computation practical for cubes of sizes 10,000 and larger.

I am hoping at some point we can get an actual implementation of the ideas presented in the paper that Bruce Norskog refers to in the previous article, and determine some numerical upper bounds as well. Bruce has already provided us with the current leading 4x4x4 upper bounds.

Will the diameter of the 4x4x4 be known in my lifetime? I suspect it will be, despite the fact that just solving a single random 4x4x4 position optimally probably requires more CPU time using current techniques than were used to determine the diameter of the 3x3x3.

  n    h-s    h-w    h-b    q-s    q-w    q-b
  2      9      9      9     10     11     10
  3     16     18     16     18     21     18
  4     32     35     29     37     41     33
  5     49     52     42     54     59     46
  6     72     75     59     80     85     64
  7     95     99     75    105    111     82
  8    124    128     96    137    143    104
  9    153    158    117    169    175    126
 10    189    193    142    208    214    152
 11    224    229    166    246    253    178
 12    265    270    194    291    298    208
 13    306    312    222    335    343    238
 14    353    359    254    386    394    272
 15    400    406    286    437    445    305
 16    452    458    321    493    501    342
 17    504    511    356    550    558    379
 18    562    568    395    612    621    420
 19    620    626    433    674    683    461
 20    682    690    475    742    751    505

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

questioning 2x2x2 value

Essentially, the 2x2x2 has one type of basic move - moving a layer with respect to its opposite layer. Thus, I would expect q-s, q-w, and q-b lower bounds to all be the same. It appears to me 10 should be the value for all 3 q metrics, while you have 11 for q-w. Of course, we know the actual God's numbers for the 2x2x2, which is 14 for QTM.

Otherwise, nice job generating this table!

2x2x2

Howdy, Bruce! I hope to post on this soon. The q-w metric on a general n x n x n turns out to be different from the others, in that the Cayley graph generated by that generator set is bipartite; every move is an odd-parity move on the corners. This is not true of any of the other metrics. Thus, the numbers in the table for the q-w metric reflect the bipartite nature of the graph.

For the five metrics that are not q-w, we find the smallest n such that the sum of c(n), c(n-1), c(n-2)... is greater than or equal to the number of positions (assuming c(n) is the recurrence relation generated by the syllable analysis). For q-w, we find the smallest n such that the sum of c(n-1), c(n-3), c(n-5)... is greater than or equal to half the number of positions.

Good eye for spotting that, by the way.

Obligatory new content: here are the numbers for a 100 x 100 x 100 cube:

  n   h-s   h-w   h-b   q-s   q-w   q-b
100 13394 13414  8469 14267 14291  8842

Yes, of course, the bipartite

Yes, of course, the bipartite structure allows extending the lower bound to 11. So arguably you could also apply the bipartite argument for q-s and q-b on the 2x2x2 since q-s and q-b are really the same thing as q-w on that cube. Then the table would have 11 for each q metric (being they are all the same metric in this case, really). As I noted, this is somewhat moot anyways, since God's algorithm has been fully computed for the 2x2x2.