June 30, 2011

Researchers Solve Rubik’s Equation

Researchers from MIT, the University of Waterloo and Tufts University have established the relationship between the number of squares in a Rubik's-cube-type puzzle and the maximum number of moves required to solve it.

The team's evidence provides an efficient algorithm for solving a cube that is in its worst-case state.

The researchers showed 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," Erik Demaine, an associate professor of computer science and engineering at MIT, said in a statement.

He said the standard way to solve a Rubik's cube is to find a square that is out of position and move it into the right place while leaving the rest of the cube as little changed as possible. 

The team found this approach will yield a worst-case solution that is proportional to N2.

The researchers 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.

"In the first hour, we saw that it had to be at least N2/log N," Demaine said. "But then it was many months before we could prove that N2/log N was enough moves."

The Rubik's cube is an example of a configuration problem, which is used to help find the most efficient way to reorganize boxes stacked in a warehouse. 

Demaine said it is possible the tools he and his team have developed for studying the Rubik's cube could be adapted to such problems.

However, he also said his research does not have to have any obvious applications.

"My life has been driven by solving problems that I consider fun," he said. "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."

An international team of researchers proved last August that no matter how scrambled a cube got, it could be solved in no more than 20 moves. 

A Rubik's cube has a total of 43 quintillion possible starting positions.


On the net: