Solving Large Rubik's Cubes within a Factor of 2.37 + o(1) of Optimal

1MIT CSAIL, Cambridge, Massachusetts, USA  ·  2Technical University of Munich, Germany  ·  3Palo Alto, California, USA

Eight evenly spaced frames from two solves, n = 65,536 above and n = 256 below. Each row runs from a fully scrambled cube to a solved one, shown both as an unfolded net and as a rendered cube.
Eight evenly spaced frames from a solve of n = 65,536 (above) and n = 256 (below), each shown as an unfolded net and as a rendered cube.

Abstract

We design optimized algorithms to solve the n × n × n Rubik's Cube within 30.5 n²/lg n + o(n²/lg n) moves. This upper bound is asymptotically within a factor of 2.37 of the known lower bound, which applies to almost all instances.

The constant 30.5 is also the first explicit constant factor for the known upper bound of O(n²/lg n), where the implicit constant of the previous algorithm was 2.01 · 1040 (twenty duodecillion). Thus we improve the upper-bound constant by a factor of more than 6.60 · 1038 (660 undecillion).

Our algorithm runs in time linear in the input size N = Θ(n²), and uses O(√ N  lg N) extra space (beyond the state of the cube). Our implementation is the first practical cube solver to generate solutions of length O(n²/lg n). It outperforms existing solvers for n as small as 840.

Video

A large partially solved cube mid-run, with its unfolded net in the corner.
Example solve using one of our proposed algorithms for n = 256.
Leading constant
30.5down from 2.01 · 1040
Of optimal
2.37×asymptotic, worst case
Largest solve
65,536cubies per edge, solved end to end