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

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