God’s number refers to the smallest number of moves required to solve any Rubik’s cube scramble. This is one of the most important mathematical concepts in cubing as it took people over 30 years to find it after the creation of the Rubik’s cube. Not only does finding this number require a lot of math, but it also requires a lot of algorithmic thinking and optimization, and the process and how this number was found may surprise you.
God’s Number
The names and dates of the different methods used to get closer to God’s Number
This value was discovered on August 12, 2009, by Tomas Rokicki and others, and was shown to be 20. Calculating it requires a bit of advanced math. If you want to get a sense of some key parts of how they did it, the first step is to represent each face of the cube as a unique integer.
Then we can represent each move on the cube as a transformation of these numbers which we can abbreviate using disjoint cycle notation. For example, doing a U move on the cube moves 1 to 3, 3 to 8, 8 to 6, and 6 to 1. Each of the 4-cycles of edges and corners would be represented in parenthesis. Mathematically, this would look like: U = (1, 3, 8, 6)(2, 5, 7, 4)(9, 33, 25, 17)(10, 34, 26, 18)(11, 35, 27, 19). We can represent all the moves on the cube just like this. If it doesn’t make sense, try following the pieces as they are shown in the parenthesis. This is just one step in the process of using many algorithms and search methods to try and find this elusive number.
After this, there were many methods and computer algorithms created to try and get as close to God’s Number as possible. Essentially, the trick is to find a lower bound and an upper bound. The lower bound would be the highest value we could guarantee to be too short to cover all the possible scrambles. For example, a scramble like U2 F R can’t be solved in less than three moves so we know that the lower bound has to be at least 3 because there is a scramble that requires at least that many moves to solve. We can keep testing this using computer simulations to find the highest lower bound.
The upper bound is a bit trickier. One thing we know for sure is that it has to be less than at least 69 moves. We know this because we can use CFOP. How? We can take the worst cases for cross, F2L, OLL, PLL, and AUF and add them up which would look something like this:
| Step | Worst Possible Case |
| Cross | 8 |
| F2L (pairs 1 and 2) | 8 |
| F2L (pairs 3 and 4) | 9 |
| OLL | 12 |
| PLL | 14 |
| AUF | 1 |
| Total: | 69 |
However, this isn’t very good. We know that 69 should be way more than the optimal solution, but now that we know what to do, all we need to do is keep increasing the lower bound and decreasing the upper bound until they meet and that’s gods number.
Kociemba’s Algorithm
What different phases of Kociemba’s algorithm may look like
To further reduce the upper bound, a group of 4 people – Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge – decided to use Kociemba’s two-phase algorithm instead of CFOP to optimize the search. Essentially, Kociemba’s algorithm split solving the cube into 2 stages. First, reducing the cube to a state that could be solved using only the moves {U, F2, R2, D, B2, L2}, and then solving the rest using only those moves in the second step. This reduces the total amount of cases to check because it splits the solving process into two smaller steps with fewer cases instead of one extremely large set of cases. Now, instead of having to check all possible scrambles in computer code, with some further optimizations, they only had to check a few billion and through the use of a lot of high-power computers at Google, they were able to do this in only a week. The result of over 30 years of hard work led to this moment and the 4 men finally discovered that God’s Number was 20. If you want to learn more, JPerm has a great video explaining the entire process in an easy-to-understand format.
The Superflip
Something to think about is the superflip pattern. This pattern is unique because it was the first Rubik’s Cube scramble to have an optimal solution of 20 moves. This was used to find the best lower bound because it was the scramble with the longest solution at the time. Could this scramble have been used to find God’s Number? Did we even need 30 years of hard work? See if you can figure out why it was so important to check all the possible orientations of the Rubik’s Cube before concluding that 20 was the lowest possible value that God’s Number could be.
Cubing Content 
Leave a comment