Computing & AIPreprintTheory4 min read

A 10⁴⁰ CONSTANT CUT TO 30.5 FOR GIANT RUBIK'S CUBES

The Rubik’s Cube, which has just turned 50, is perhaps the best-known puzzle in the world, and one of its central questions is simple to state: in the worst case, how many moves does it take to solve? For the classic 3×3×3 cube, the answer is known exactly: 20 moves, a result published in 2014 by a team that included Tomas Rokicki, one of the authors of this new paper.

For bigger cubes, with n layers along each edge, the exact answer is out of reach — finding the shortest solution for a given n×n×n cube is even NP-complete, a class of problems for which no efficient method is known. But in 2011, Erik Demaine and colleagues showed how the worst case grows: in proportion to n² / lg n, where lg is the base-2 logarithm. That is a logarithmic factor better than standard methods, which solve the pieces essentially one at a time.

A proof with an absurd constant

There was a catch. The 2011 result guaranteed the growth rate, not the number in front of it. Working through that algorithm, the authors find that its constant is about 1.01 × 10⁴⁰, ten duodecillion. The culprit is a computer check that proved certain moves could reach every arrangement of a group of 24 pieces, without saying how quickly. The only safe bound on that length was the size of that group of arrangements, about 3.1 × 10²³ steps, and the formula ends up using the huge number 24! (1 × 2 × … × 24, about 6.2 × 10²³) in two places. By contrast, the lower bound — the number of moves that almost every scrambled cube needs — has a modest constant of about 12.88. Many in the community therefore believed such an algorithm could never be practical for reasonable sizes.

Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf and Erik Demaine, from MIT, TU Munich and Palo Alto, have now made that constant explicit and small.

Sorting networks for cube pieces

On a big cube, the centre pieces dominate: their number grows as n², while corners and edges only add terms proportional to n. Centre pieces fall into families of 24 that can only swap among themselves. The basic tool is the commutator, a sequence of the form A B A′ B′ — do A, then B, then undo A, then undo B — that leaves almost everything in place and permutes just three pieces of one family. The team found move sequences for all 4,000 usable three-piece swaps, each at most 12 moves long.

Two ideas make the count drop. First, the same commutator can be applied to many families at once, across whole groups of rows and columns. Second, instead of solving each family on its own, every family follows one fixed universal sequence of swaps, simply skipping the ones it does not need. A lemma ties everything together: a universal sequence of L stages gives a leading constant of L/2.

Shortening that sequence borrows tools from computer science’s sorting networks, fixed patterns of comparisons that sort any input. An optimal six-input sorting network gives 96 stages, hence a constant of 48. Networks splitting the 24 positions into groups of 12, then 4, found by computer search, bring it to 72 stages, hence a constant of 36. Finally, allowing moves that shuffle more than three pieces at once and splitting the positions differently brings it to 61 stages.

Thirty point five

The theorem: any n×n×n cube can be solved in at most 30.5 n²/lg n moves, plus terms that become negligible for large n. The constant improves by a factor of more than 3.30 × 10³⁸, and sits within a factor of 2.37 of the lower bound (30.5 / 12.88). For the flat n×n×1 version, used as a warm-up, the constant drops from 12 or 18 to 1.5.

Eight frames of a 256-layer cube being solved, shown as unfolded faces and as small cubes, from scrambled noise to solid colours.

Eight evenly spaced frames of a solve of a cube with 256 layers per side: the scrambled faces turn into solid colours. — Figure 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

The algorithm runs in time proportional to the number of pieces, and the authors provide an open-source solver, with scripts that exhaustively check every network it relies on. Their own comparison finds it ahead of existing solvers from about n = 840; they have rendered solves of cubes with 256 and 65,536 layers per side.

The 2.37 is an asymptotic statement: the formula’s smaller terms are not pinned down, so it does not give an exact count for a specific cube. Future gains, the authors suggest, may come from other ways of grouping pieces into sorting networks and from better three-piece swaps — and the same machinery could tackle other giant puzzles, or four- and five-dimensional hypercubes.