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