Erik Demaine - The math of the Rubik's cube
New research establishes the relationship between the number of squares in a Rubik's cube-
type puzzle and the maximum number of moves required to solve it.
Larry Hardesty, MIT News Office
June 29, 2011
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,"
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.
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."