Question: What is the maximum number of moves required to solve a Rubik's cube?
Nobody knows the answer yet. But it's either 21, 22, or 23 moves, and we're about to find out which one: we've got a determined programmer with a huge super-computer on the case.
Rapid Recent Progress. In 2006, Tom Rokicki showed that there are cube configurations requiring at least 20 moves to solve; this gave us a lower bound. Then last year, Kunkle and Cooperman proved (pdf) that any cube configuration can be solved in 26 moves; this gave us an upper bound.
But in recent months, rapid progress has been made. In March, Rokicki developed and posted a highly effecient solution-finding algorithm, with which he was able to reduce the upper bound to 25 moves. He now says he's already reduced that number to 23, and is currently working on 22.
Clearly this will all be over soon. In the worst case, Rokicki will have to keep going until he shows that every cube position can be solved in 21 moves -- then this would be the maximum, and the problem would be solved.
Solving a Rubik's Cube. There are roughly 40 quintillion possible positions on a Rubik's cube -- that's 40 with 19 zeros after it. So even a super-computer that can check a trillion cube positions a second (which doesn't exist) would require a length of time equal to the current age of the Universe in order to check every position.
The plan of attack is thus to vastly reduce the number of cube positions to be checked, and then apply a very efficient algorithm. Rokicki's algorithm, together with 8 GB of memory, allowed him to clip through 16 million positions per second, and gave him the 25 move upper bound. This algorithm is based on a similar algorithm developed by Herbert Kociemba, and used in his fascinating Cube Explorer software (which you can download for free).
However, to produce his most recent results, Rokicki had to head over to Sony Pictures Imageworks. Sony lent Rokicki their super-computers during the idle-time between productions, which allowed him to grind through cube positions much more quickly. Yes, the very same computers that brought you Spiderman 3 now bring you "God's Algorithm" for the Rubik's Cube. Unfortunately, you won't be able to impress your friends with arbitrary 23-move solutions using your laptop -- the computing power you would need is enormous.
History of Solutions. The Rubik's cube was developed in the 70's in Hungary, and released internationally in 1980. The first popularly distributed solution was published in David Singmaster's (1981) Notes on Rubik's Magic Cube.
Operating a Rubik's cube forms a mathematical group, the Cube Group. Knot theorist Morwen Thisthlethwaite, who was Singmaster's office-mate, noticed that subgroups of the Cube Group could be systematically described as nested one within the other. He was able to exploit this structural feature in order to produce an algorithm that solves the cube in a maximum of 52 moves.
Thistlethaite's approach is the kind of solution that one's inner-mathematician would really like to see: a solution that actually teaches us something about the structure of the Rubik's cube. Rokicki's brute-force combinatorics approach offers little in this regard, despite its practical effectiveness.
Toward the mathematical end, Douglas Hofstadter suggested in 1981 (reprinted here, chapter 14) that there are sophisticated group theoretic arguments pointing to an upper bound of 22 or 23 moves. Frey and Singmaster also conjectured in 1982 that the maximum number of moves required to solve the cube may be in the low 20's. These arguments are in intriguing agreement with Rokicki's results. However, the group theorists have made little progress on the problem since then, and so a super-computer generated solution may be all we can expect in the near future.
Updated 11 hours ago