The Rubik’s Cube: we have probably all tried to solve it. Some of us failed to do it and some of us have found real successes. The 3-D combination puzzle was invented in 1974 by the Hungarian sculptor and professor of architecture Ernő Rubik. As of March 2021, over 450 million cubes had been sold, making it the best-selling toy in history. The puzzle has become so popular, that even championships of who can solve the Rubik’s Cube the fastest are being held. For example, an interview done by Sjors Keet with two-fold world champion Mats Valk can be read here . Moreover, mathematicians love the Rubik’s Cube. They are amazed at how this simple concept holds so many secrets. This made them wonder: what is the maximum number of moves required to solve a Rubik’s Cube?
Permutations
Before we will look at the maximum number of moves required to solve a Rubik’s Cube, we will first look at the number of possible combinations the cube gives us. We know that solving the cube isn’t as simple as just rotating the faces until it’s solved. The number of possible combinations is so high, that it can’t be finished by just randomly turning the faces. The total number of ways you can scramble the 3×3 cube is 43,252,003,274,489,856,000. We can write this in a more mathematical way as follows: $\frac{3^8 8! 2^{12} 12!}{12}$. This comes together in the following way:
At first, $3^8$ counts every way the eighth corner cubies can be rotated. We namely have eighth corner cubies, that can fit into its slot in three different ways. This is multiplied by the place where each corner cubie goes. The first cubie has eighth options, the second has seven, etc. This gives us $8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 8!$. Then, $2^{12} 12!$ uses the same idea, but for the edge cubies. There are twelve edges, which have two orientations and twelve possible locations.
Lastly, this sum is divided by twelve. Here, we need a bit of intuition. If you break open a Rubik’s Cube, remove each cubie and put it back in place in a random spot, you get what looks like a normal mixed-up cube, giving us the $3^8 8! 2^{12} 12!$ different permutations. However, it is not always possible to solve this randomly scrambled cube without breaking the whole cube apart. If you break the cube apart and put the pieces back randomly, there is actually only a chance in one of twelve of solving the cube, thus giving us the fact that the sum is divided by twelve.
God’s number
So, now that we know the number of permutations a Rubik’s Cube has, what is the maximum number of moves required to solve any of these 43,252,003,274,489,856,000 combinations? We say that if you solve a Rubik’s Cube, you use an algorithm, or a sequence of steps for solving the cube. We then suppose that God would use the most efficient algorithm, which is the shortest sequence of moves. This is known as God’s Algorithm. Then, the number of moves this algorithm would use in the worst case is called God’s number. Spoiler alert: this number turned out to be twenty.
How God’s number was found
Finding the magic number twenty took mathematicians about thirty years. The ultimate trick to finding God’s number is just to write some code. Here, you first generate the 43 quintillion positions, then try every sequence of moves to solve each scramble, record how many moves that took and then just wait for the code to run through all the scrambles. Then, you have a list with all the solution lengths and the longest one would tell you what God’s number is. However, the amount of time the code would run, would most certainly outlive your great great granddaughter. Hence, a smarter approach was found. God’s number was approached from two sides: the upperbound and the lowerbound. If the lower bound at the end equals the upper bound, you have found God’s number. In 1980, a lower bound of eighteen was found. This was done by analyzing the number of effectively distinct algorithms of seventeen or fewer moves, and finding that the number of algorithms was lower than the 43 quintillion combinations. In 1981, Morwen Thistlewaite found an upper bound of 52 moves using a complex algorithm. As can be seen in the graph below, this upper bound became lower and lower as more efficient methods were used.
Graph from In 1995, a lower bound of twenty was found by Michael Reid. Here, he proved that solving the ‘superflip’ position required twenty moves. This position can be recognized by the fact that all the corners are solved in their place, while all edges are flipped in their place. In 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge proved that God’s number is exactly twenty. To prove this theory, not all the 43 quintillion combinations were tested individually. This is due to the fact that rotating the puzzle gives us new positions, but not more unique patterns. Therefore, there are 24 ways to position the cube for all scrambles. Hence, only 4% of the positions need to be tested, resulting in 1,802,166,800,000,000,000 different combinations. This number was further reduced to 55,882,296 sets, by factoring in other similarities, such as mirrors. However, to run all of these cases, an extremely powerful computer was needed. Here, Google came to the rescue. The mathematicians managed to run about 35 CPU-years in just a few weeks. They then proved that God’s number was exactly twenty.
Half-turn metric vs. quarter-turn metric
What we do have to mention is that God’s number of twenty uses the half-turn metric. This half-turn metric explains how moves are counted. Here, a quarter turn and a half turn are both a single move. However, there also is another method to count moves. There, only quarter turns are counted as one move and half turns are counted as two moves. This is called the quarter-turn metric. In 2014 it was found by Tomas Rokicki and Morley Davidson that God’s number in quarter-turn metric is 26.
Are we done?
So, now that we have found God’s number for the half-turn metric and the quarter-turn metric, are mathematicians done with finding it? Not slightly. Many more God’s numbers are to be found, for example for the 4×4 and 5×5 Rubik’s Cube. However, if you can’t get your number of moves per solve to drop as low as twenty, don’t be worried. The average speed-solver takes between 50 and 60 moves per solve.