Last August, 30 years after the Rubiks cube first appeared, an international team of researchers proved that no matter how scrambled a cube got, it could be solved in no more than 20 moves. Although the researchers used some clever tricks to avoid evaluating all 43 quintillion of the cubes possible starting positions, their proof still relied on the equivalent of 35 years worth of number crunching on a good modern computer.
Unfortunately, for cubes bigger than the standard Rubiks cube with, say, four or five squares to a row, rather than three adequately canvassing starting positions may well be beyond the computational capacity of all the computers in the world. But in a paper to be presented at the 19th Annual European Symposium on Algorithms in September, researchers from MIT, the University of Waterloo and Tufts University establish the mathematical relationship between the number of squares in a cube and the maximum number of moves necessary to solve it. Their method of proof also provides an efficient algorithm for solving a cube thats in its worst-case state.
Computer science is concerned chiefly with the question of how long algorithms take to execute, but computer scientists measure the answer to this question in terms of the number of elements the algorithm acts upon. The execution time of an algorithm that finds the largest number in a list, for instance, is proportional to the length of the list. A dumb algorithm for sorting the numbers in the list from smallest to largest, however, will have an execution time proportional to the square of the length of the list.
Solution with a twist
Erik Demaine, an associate professor of computer science and engineering at MIT; his father, Martin Demaine, a visiting scientist at MITs Computer Science and Artificial Intelligence Laboratory; graduate student Sarah Eisenstat; Anna Lubiw, who was Demaines PhD thesis adviser at the University of Waterloo; and Tufts graduate student Andrew Winslow showed that the maximum number of moves required to solve a Rubiks cube with N squares per row is proportional to N2/log N. That thats the answer, and not N2, is a surprising thing, Demaine says.
The standard way to solve a Rubiks cube, Demaine explains, is to find a square thats out of position and move it into the right place while leaving the rest of the cube as little changed as possible. That approach will indeed yield a worst-case solution thats proportional to N2. Demaine and his colleagues recognized that under some circumstances, a single sequence of twists could move multiple squares into their proper places, cutting down the total number of moves.
But finding a way to mathematically describe those circumstances, and determining how often theyd arise when a cube was in its worst-case state, was no easy task. In the first hour, we saw that it had to be at least N2/log N, Demaine says. But then it was many months before we could prove that N2/log N was enough moves.
Because their method of analysis characterizes the cases in which multiple squares can be moved into place simultaneously, it provides a way to recognize those cases, and thus an algorithm for solving a disordered cube. The algorithm isnt quite optimal: It always requires a few extra moves. But as the number of squares per face increases, those moves dwindle in significance.
The Rubiks cube is an instance of whats called a configuration problem, the best-known example of which involves finding the most efficient way to reorganize boxes stacked in a warehouse. Its possible, Demaine says, that the tools he and his colleagues have developed for studying the Rubiks cube could be adapted to such problems.
But Demaine is also a vocal defender of research that doesnt have any obvious applications. My life has been driven by solving problems that I consider fun, he says. Its always hard to tell at the moment what is going to be important. Studying prime numbers was just a recreational activity. There was no practical importance to that for hundreds of years until cryptography came along.
But, he adds, the aesthetic is not just to look at things that are fun but also look at problems that are simple. I think the simpler the mathematical problem, the more likely that its going to arise in some important practical application in the future. And the Rubiks cube is kind of the epitome of simplicity.
Erik is always very interested in extending the reach of popular mathematics, says Marc van Kreveld, an associate professor in the Department of Information and Computing Sciences at Utrecht University in the Netherlands, who designs puzzles in his spare time. Thats really one of the things that he tries to do, to bring across that mathematics is not just some boring area of study, but its actually fun, and you can do a lot with it, and its beautiful.
Eriks a very brilliant person, van Kreveld adds. He is already very successful in his hard-core research. But the popularizing is also very necessary, I think. You should not underestimate the importance of motivating students to learn.
Explore further: Copying behavior in social groups may be governed by optimal control theory