Math of the Rubik's Cube
It's rare for mathematical research to break into the mainstream media. New papers are posted on the arXiv every day, and published in journals all over the world throughout the year, but unless a famous problem is purported to have been solved (in this case, a famous problem is usually one that has a cash prize associated with its solution), knowledge of such advances is only found by those specifically seeking it. Last week, however, there an exception to this general rule was made for a new result concerning the Rubik's cube.
The conclusion, reached by an international team of mathematicians, is that the Rubik's cube can always be solved in 20 moves or less, and that, moreover, their result is in some sense the best possible. This result was featured on the front page of Yahoo News for a couple of days, which I found surprising.
What do I mean by "best possible"? Well, since 1995 it's been known that the minimum number of moves needed to solve a Rubik's cube is at least 20 - in other words, it was proven that there exists a configuration of the Rubik's cube which is solvable in 20, but no fewer than 20, moves. But it was not clear if this could be improved - after all, once this result has been proven, is it possible to find a cube that needs 21 moves to be solved? What about 22? or 25? or 1,000?
In the same year, it was shown that the maximum number of moves could be bounded above by 29. So, for the past 15 years, we have known that every possible configuration of the Rubik's cube (of which there are 43,252,003,274,489,856,000) can be solved in somewhere between 20 and 29 moves. The question, since then, has been to narrow this gap in order to find the smallest number of moves for which every configuration is actually solvable.
So, we now know that number is 20. The researchers who discovered this fact have created a website in honor of it, in which you can learn more about this history of the problem, as well as see examples of configurations that require exactly 20 moves to solve.
For those of you who may fancy yourselves Rubik's cube hobbyists, however (yes, Will Smith, I am talking to you), it's unlikely that you can solve a Rubik's cube in such a small number of moves. When people learn techniques to solve Rubik's cubes, they are necessarily techniques that are simple enough for a human to remember. This means that they may not always be the most efficient. But now we know that even with the most efficient approach, there are some times when 20 moves will be needed.
For this reason, 20 is referred to as "God's number." Yes, I thought it sounded a little pretentious too. The reasoning is that an omniscient being would presumably choose the most efficient algorithm. Although my feeling is that God has better things to do than solve Rubik's cubes.
In any event, the Rubik's cube is a rare piece of pop culture iconography in that there are a substantial number of advanced mathematical questions one can ask about it. Mostly this is because the transformations of the Rubik's cube that you perform when you try to solve it (or, if you are a jerk, the transformations that you perform when you try to screw up somebody's solved one) endow the cube with a group structure; in less technical terms, it means that composing two transformations gives a transformation, there is an identity transformation (the transformation that doesn't do anything), every transformation is invertible (every move you make can be reversed), and transformations are associative (given transformations a, b, and c, applying a to the composition of b and c is the same as applying the composition of a and b to c). The curious reader can find more about the Rubik's cube group here.
The Rubik's cube also holds the distinction of being the only mathematical object (that I'm aware of) that had a starring role in an 80's cartoon show. Who knew that anthropomorphic Rubik's cubes could be so creepy looking?
While some readers may be excited by this discovery, others are undoubtedly less impressed. After all, the Rubik's cube is just a silly game, isn't it? Knowing that it can be solved in under 20 moves doesn't advance our understanding of how the world works, does it? Furthermore, a brief examination of their argument reveals that much of the work involved was manual checking of billions of separate cases by computer. This is not an elegant solution by any means - while this certainly gives a proof of God's number, it not a proof from The Book.
On the other hand, there are ideas going on here that are interesting and have been asked in a general context. For example, the notion of taking a finite group and a set of generators for that group, and asking how many generators you need to get to any element of the group, has been studied before (such a number is referred to as the diameter of that group with respect to the set of generators). In general, the problem of calculating the diameter of a group is quite hard, so having an example in which the diameter is known is helpful, regardless of where that example comes from.
Besides, in the words of the Joker, why so serious? Not all results have to shatter the way we perceive the world. Math should be recreational, too. Having said that, I have mixed feelings about this result being used as representative of what mathematicians do, for reasons I've stated before. Mathematics is more about ideas than it is about brute force calculation (although the latter is sometimes necessary). Of course, there are ideas involved in reducing the number of cubes to consider, so that the calculations can be carried out in a reasonable time frame. Also, I understand why a result like this can capture the public's imagination: it's easy to state for a general audience.
The result raises other questions as well: what if we consider an n by n by n cube, for general 3 x 3 x 3? What's the minimum number of moves needed to solve every 2 x 2 x 2 cube, for example, or every 4 x 4 x 4 cube? Intuition tells me that the amount of computation involved may grow quite rapidly as n increases, so we may not be able to answer this question for many values of n, but since the 3 x 3 x 3 case is known, it shouldn't be hard to solve the 2 x 2 x 2 case (in fact, the solution is known: in this case, God's number is 11). What about general Rubik's blocks, where the shapes may not be cubes?
Another question: we know that in the 3 x 3 x 3 case, God's number is 20. But how frequent are the positions that require 20 cubes to solve? Are they rare, and in most cases do we expect that 20 can be improved? In other words, what is the proportion of worst-case scenarios? This question is addressed on the new Rubik's Cube website mentioned earlier. Of course, analogous questions can be formulated for more general cubes.
And as is frequently the case in mathematics, this result is not without controversy. For even though these researchers claim to have shown that you can't do better than 20, the video below highlights a method that can be used to solve any Rubik's cube in just one move! (Spoiler alert: yes, a Rubik's cube will blend).
Psst ... did you know I have a brand new website full of interactive stories? You can check it out here!
comments powered by Disqus