14 DAY TRIAL // Researchers at the Massachusetts Institute of Technology (MIT), in Cambridge, say that they were able to determine the mathematical connection between the number of squares in a Rubik's Cube and the maximum number of moves a player must perform in order to solve the mechanical puzzle.
Last year, more than three decades after Ernő Rubik invented his famous toy, experts with an international group were able to determine that 20 moves is all it takes to solve a Cube, regardless of how mixed up it is at its starting position.
The team, which presented its results last August, used a series of mathematical tricks to avoid having to compute all the possible 43 quintillion starting positions that a standard, 3x3x3 cube has.
Experts used a supercomputer to calculate the number of moves necessary to solve the cube. Their simulation used the equivalent of 35 years of computing on a modern home computer.
But the team acknowledged that the larger the Cubes grow, the more difficult it becomes to calculate the maximum number of moves. Advanced Rubik's Cubes can have more than 3 squares per row. The largest is a 7x7x7 monster (V-Cube).
Calculating all the starting positions for a V-Cube is probably beyond the computational limits of even the most advanced supercomputers. But MIT, University of Waterloo and Tufts University experts argue that performing these calculations is unnecessary.
In a paper to be presented at the 19th Annual European Symposium on Algorithms this September, the team says that the relationship it discovered – which connects the number of squares in a cube to the maximum number of moves needed to solve it optimally – eliminates the need for such calculations.
Additionally, using the new method, researchers also developed an extremely-efficient algorithm, that allows a player to resolve a Rubik's Cube with the minimum of movements, even if the Cube is in its worst possible initial arrangement.
The maximum number of moves a player needs to perform in order 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,” says MIT Computer Science and Artificial Intelligence Laboratory visiting scientist Martin Demaine.
Solving the mathematical mysteries related to the Rubik's Cube has been a long-time goal for researchers, ever since the mechanical puzzle was introduced, back in 1974.
The Cube is the top-selling puzzle game and the best-selling toy in the world. By 2009, more than 350 million Cubes had been sold around the world.