A Demigod’s Number for the Rubik’s Cube
Arturo Merino †, Bernardo Subercaseaux ‡ · 2025
Read A Demigod’s Number for the Rubik’s Cube by Arturo Merino †, Bernardo Subercaseaux ‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00144.txt.
Introduction
Arturo Merino and Bernardo Subercaseaux set a loose but easy-to-check bound on solving the Rubik's Cube, in work published in 2024. Any cube state can be solved in at most 20 moves, but proving that took huge computer time and is hard to repeat. The pair offer a simpler route to a weaker claim.
Their idea uses the even spread of cube states. For such even graphs, the mean gap between states is at most half the widest gap. Sampling random states and solving them gave a mean near 18 moves. A standard bound then supports a widest gap of at most 36 moves with high confidence. The trick works for other even graphs too.
Catalog record
| CREATOR | Arturo Merino †, Bernardo Subercaseaux ‡ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00144
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Demigod’s Number for the Rubik’s Cube Arturo Merino †, Bernardo Subercaseaux ‡ Abstract It is by now well-known that any state of the 3 × 3 × 3 3\times 3\times 3 Rubik’s Cube can be solved in at most 20 moves, a result often referred to as “God’s Number” . However, this result took Rokicki et al. around 35 CPU years to prove and is therefore very challenging to reproduce. We provide a novel approach to obtain a worse bound of 36 moves with high confidence, but that offers two main advantages: (i) it is easy to understrand, reproduce, and verify, and (ii) our main idea generalizes to bounding the diameter of other vertex-transitive graphs by at most twice its true value, hence the name “demigod number” . Our approach is based on the fact that, for vertex-transitive graphs, the average distance between vertices is at most half the diameter, and by sampling uniformly random states and using a modern solver to obtain upper bounds on their distance, a standard concentration bound allows us to confidently state that the average distance is around 18.32 ± 0.1 18.32\pm 0.1 , from where the diameter is at most 36 36 . 1 Introduction The 3\times 3\times 3 Rubik’s Cube, illustrated in Figure 1 , is arguably one of the most iconic puzzles ever created, and one of the best-selling toys of all time; its beautiful balance of simplicity (it only has 6 faces, with 54 colored stickers) and complexity (it has over 4.3\times 10^{19} possible states) has captured the attention of millions of people around the world since its invention in 1974. Naturally, such a combinatorially rich puzzle has raised a variety of interesting mathematical questions, with the most famous one being: What is the minimum number of moves required to solve the Rubik’s Cube from any starting position? To make this question precise, we consider the half-turn metric , in which turning either of the 6 faces of the cube by any amount (i.e., 90^{\circ} , 180^{\circ} , or 270^{\circ} ) counts as a single move. After a series of incremental improvements detailed in Table 1 , Rokicki et al. [ 22 ] proved that 20 moves are always enough to solve any Rubik’s cube in the half-turn metric, a result often referred to as “God’s Number” . This result, however, was obtained by a mixture of mathematical ideas and extensive computation, taking around 35 CPU years. As a result, verifying the correctness of the so-called God’s Number is extremely challenging, and the required computations have likely never been reproduced independently. While the result is widely believed to be true, our goal is to provide an alternative approach (providing a weaker bound) that can be easily understood and reproduced in e.g., a classroom setting. Table 1 : Historical bounds on the maximum number of moves required to solve the Rubik’s Cube [ 20 ] . Year Lower bound Upper bound 1981 18 52 1990 18 42 1992 18 39 1992 18 37 1995 18 29 1995 20 29 2005 20 28 2006 20 27 2007 20 26 2008 20 25 2008 20 23 2008 20 22 2010 20 20 1.1 Summary Our approach is based on the following observation: in any vertex-transitive graph (i.e., a graph where every vertex “looks the same” ), the diameter D (i.e., the maximum distance between any two vertices) is at most twice the mean distance between vertices, m . This observation corresponds to a question posed by Alan Kaplan [ 24 ] , which was answered in the more general context of homogeneous compact metrics spaces by Herman and Pakianathan [ 11 ] . Our proof, however, is elementary and self-contained, and we believe it can be a nice addition to a first course on graph theory. Applying the previous observation to the Cayley graph of the Rubik’s cube (defined formally in Section 2 , this graph has the possible states of the cube as vertices and edges between pair of states that are one “move” away from each other), if we knew the average distance \mu between states of the Rubik’s Cube, we could bound the diameter of the Rubik’s Cube by at most twice this value. While we cannot directly compute the exact value of \mu for the Rubik’s Cube 1 1 1 Recall that it has over 4\cdot 10^{19} many states. , we can provide a good estimate by sampling random pairs of states and computing an upper bound on their distance through standard Rubik’s algorithms (i.e., Kociemba’s Two-Phase Algorithm [ 17 ] ). Each of these upper bounds for the distance between a pair of states is certified by a short sequence of moves, so one can trust the result without needing to trust the algorithm. Through simple concentration bounds, we will argue that the empirical average of \widehat{\mu}\approx 18.3189 we obtain is overwhelmingly likely to be a good estimate of the true mean distance \mu , and therefore an audience should reasonably trust that the diameter of the Rubik’s Cube is at most 36 (since it must be an integer). As a first step, we will prove the following theorem. Theorem 1 . Given a state s of the Rubik’s Cube, let d(s) be the distance from s to the solved state. Let S be a set of states of the Rubik’s cube sampled uniformly at random, and let \widehat{\mu}_{S}=\frac{1}{|S|}\sum_{s\in S}d(s) be the random variable corresponding to the average distance between states in S and the solved state. Then, if D denotes the diameter of the Rubik’s Cube, we have \Pr_{S}\left[D\geq 2\widehat{\mu}_{S}+0.36\right]<2\exp\left(\frac{-|S|}{1\,541\,939}\right). Note immediately that Theorem 1 implies that if D>36 (and thus D\geq 37 since the diameter is an integer), the probability of obtaining \widehat{\mu}_{S}\approx 18.318 for |S|=10^{7} is less than 10^{-7} . However, this experience can be observed repeatedly, which is therefore a great degree of probabilistic evidence for D\leq 36 . Unfortunately, Theorem 1 is somewhat computationally expensive, as it requires the number of samples |S| to be around 10 million if we desire a probability of error under 10^{-7} . As we show in Section 4 , this takes roughly 100 hours of computation. In order to see how to reduce the required computation, let us briefly discuss how Theorem 1 is obtained. To obtain an upper bound on D , we can leverage the D<2\mu observation and look for an upper bound on \mu , which we can do with a probabilistic guarantee by considering an empirical average \mu_{S} . However, a priori it could be that the true average \mu is much larger than our empirical estimate \mu_{S} due to a small number of states that are very far and we are not likely to sample randomly; a “long tail” phenomenon. Our solution to this problem is using a “Human’s number” , which is an unconditional modest upper bound on D . For instance, the so-called “beginner’s method” suffices to obtain an upper bound of 205 moves. Lemma 1 (Human’s Number) . Any position of the Rubik’s cube can be solved in at most 205 moves. 2 2 2 A proof sketch is provided in the appendix. In general, we expect anyone familiar