THE SCIENCE OF RUBIK'S CUBE

THE SCIENCE OF 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.

An interview from Larry Hardesty, MIT news office tells us about the science behind the Rubiks Cube

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.

To know more secrets about the rubik's cube click here.