Last August, 30 years after the Rubik’s 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 cube’s 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 Rubik’s 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 that’s 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 MIT’s Computer Science and Artificial Intelligence Laboratory; graduate student Sarah Eisenstat; Anna Lubiw, who was Demaine’s 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 Rubik’s cube with N squares per row is proportional to N2/log N. “That that’s the answer, and not N2, is a surprising thing,” Demaine says.
The standard way to solve a Rubik’s cube, Demaine explains, is to find a square that’s 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 that’s 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 they’d 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 isn’t quite optimal: It always requires a few extra moves. But as the number of squares per face increases, those moves dwindle in significance.
Go configure
The Rubik’s cube is an instance of what’s called a configuration problem, the best-known example of which involves finding the most efficient way to reorganize boxes stacked in a warehouse. It’s possible, Demaine says, that the tools he and his colleagues have developed for studying the Rubik’s cube could be adapted to such problems.
But Demaine is also a vocal defender of research that doesn’t have any obvious applications. “My life has been driven by solving problems that I consider fun,” he says. “It’s 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 it’s going to arise in some important practical application in the future. And the Rubik’s 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. “That’s really one of the things that he tries to do, to bring across that mathematics is not just some boring area of study, but it’s actually fun, and you can do a lot with it, and it’s beautiful.”
“Erik’s 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:
Mathematicians analyze social divisions using cell phone data
