The Demigod’s Shortcut

God’s Number for the Rubik’s Cube is 20 — every configuration can be solved in at most 20 moves. Proving this required 35 CPU-years of computation: an exhaustive enumeration of the cube’s 4.3 × 10^19 states, compressed through symmetry but still enormous. The proof is correct and complete. It is also impenetrable to human intuition.

Merino and Subercaseaux (arXiv:2501.00144) prove a weaker but far more elegant bound: at most 36 moves. The proof is short enough to fit on a few pages.

The argument exploits vertex-transitivity. The Rubik’s Cube group acts transitively on its state space — every state looks the same as every other from the graph’s perspective. In a vertex-transitive graph, the average distance between any two nodes cannot exceed half the diameter. So if you can estimate the average distance, you get a bound on the maximum distance.

They estimate the average distance by sampling. Pick random configurations, solve them with modern solvers, record the solution lengths. The average comes to approximately 18.32 moves, with tight confidence intervals. Since average ≤ diameter/2, the diameter is at most 36.

The factor-of-2 looseness is the price of simplicity. But the method generalizes: for any vertex-transitive graph, random sampling plus concentration inequalities bounds the diameter to within a factor of 2. The authors call this the “demigod’s number” — not omniscient enough for the exact answer, but powerful enough for a guaranteed approximation.

The structural lesson: the gap between exact and approximate results can be the gap between 35 CPU-years and a napkin calculation. The exact answer (20) required exhaustive computation. The approximate answer (≤ 36) required only the symmetry of the problem and a handful of random samples.

Merino & Subercaseaux, “A Demigod’s Number for the Rubik’s Cube,” arXiv:2501.00144 (2025).