God’s number | mathematical musings

After thirty years of people thinking about it, a famous open problem about the Rubik’s Cube has finally been resolved: God’s number is 20. In other words, every Rubik’s Cube, no matter how mixed up, can be solved in 20 moves or less. A nice summary of the work can be found at: http://www.cube20.org/

This enormous calculation was completed by a team of Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki, and oh yes, 35 CPU-years of idle computer time donated by Google. The preprint should be available by early September sometime.

It should be noted that for quite a while “God’s algorithm” has been known — in other words computers could quickly solve any given position with a minimal number of moves. But even with the algorithm in hand, to get God’s number by brute force would take too long, since there are $4.3 \times 10^{19}$ possible positions and one would have to check that they can all be solved in 20 moves or less. To get around checking this humongous number of positions required a lot of ingenuity and not only computing muscle, and the team should be warmly congratulated.

For the rest of this note, I’d like to briefly discuss a tiny bit of the mathematics involved, and an open problem or two.

First of all we should be clear about what we mean by “20 moves” — this is in the half-turn metric (HTM), where a move consists of turning any side, by either a quarter turn or a half turn. So to mathematicians, “God’s number” is the diameter of the Cayley graph for the generating set $\langle L, R, U, D, F, B, L^2, R^2, U^2, D^2, F^2, B^2 \rangle$ . This is the metric of choice for cubers, and probably has been for thirty years. To cubers turning a side is turning a side.

Of course a half turn is just two quarter turns, and this leads us to consider the quarter-turn metric (QTM), where we only allow turning any side a quarter turn. Of course you can still give it a half turn, but now this counts as two moves. What is the diameter of the Cayley graph for the generating set $\langle L, R, U, D, F, B \rangle$ ? This is probably a more natural generating set to mathematicians, who might resist including both $x$ and $x^2$ in the list of generators for a group.

It is now known (due to a calculation by Rokicki) that 29 moves are always sufficient, and he suspects that the methods used to show that 20 suffice for HTM could probably easily bring this down to 28.

On the other hand, there is essentially only one position known that requires 26 moves in the QTM, and only two in that require 25 moves. This is a very different situation than HTM, where there are roughly 300 million positions distance 20 from solved. Extensive searches by Rokicki have failed to find any more positions requiring 25 or 26 moves. So the conjecture is that the diameter of the Cayley graph with the QTM generators is 26, but it might be a while before we know that for sure. In particular the methods applied to solve HTM apparently don’t work quite as cleanly as they do for QTM.

So this is one problem: show that God’s number for quarter-turn metric is 26.

What might be nice to see, for either metric, is a description of the geometry or topology of the Rubik’s cube. One could imagine, for example, adding higher dimensional cells to extend the Cayley graph to a polyhedral complex, and studying the topology of this complex.

Finally, the following also seems to be wide open: if one makes random moves on the cube (i.e. takes a random walk on one of the Cayley graphs), what can be said about the Markov chain mixing time? A famous result of Bayer and Diaconis is that it takes “seven shuffles” to mix up a deck of 52 cards, and it would be mathematically nice to have such an answer for the Cube. (The diameter of the Cayley graph being 20 puts an upper bound on the mixing time, but the bound obtained in this naive way is much too large to be close to the truth.)

But unlike the card shuffling, which actually has some practical application, at least for (say) casinos who want to make sure their decks are randomized, this would be purely for knowledge and enjoyment. Apparently this kind of mixing time question was once an issue for speed-solving tournaments, as they would make a sequence of random moves to mix up the cube, and one might want to know how many random moves to make. But this is no longer an issue — instead of choosing a sequence of random moves, now they have the computer choose a random position uniformly from all $4.3 \times 10^{19}$ positions, and then use God’s algorithm to put the cube into that position.

(Special thanks to Tom Rokicki for very helpful conversations in writing this note.)