Scientists have cranked through the numbers and determined that no matter how you mangle a Rubik’s Cube, if you’re doing it right you can theoretically solve the puzzle in 20 moves or fewer. By doing it right, we mean doing it like a supercomputer: Researchers tapped Google’s spare computing power to burn through the Cube’s 43,252,003,274,489,856,000 starting positions.

Even given Google’s processing power, the team–which included a mathematician, a Google engineer, a math teacher, and a programmer–could not solve the problem using brute force alone. They had to take all the starting positions and divide them into more manageable chunks, 2.2 billion smaller groups called “corsets,” which Google’s computers could solve simultaneously.

“The primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate,” says Tomas Rokicki, a programmer from Palo Alto, California, who has spent 15 years searching for the minimum number of moves guaranteed to solve any configuration of the Rubik’s cube. [New Scientist]

Though smaller, these 2.2 billion groups also each had about 20 billion starting positions.

The subproblems were small enough to fit in the memory of a modern PC. But it would take an Intel four-core, 2.8-GHz Nehalem chip-based desktop computer 1.1 billion seconds, or about 35 years, to perform the calculation. So the team turned to the impressive computing power that Google has to solve the problem. (Google won’t disclose exactly what kind of computing resources it offered to the group.) [Wired]

Mathematicians have slowly whittled down the believed minimum number of moves to solve the Cube from any starting position, the so called “God’s number,” since the Cube’s creation in 1974 by Hungarian Erno Rubik. Many believed that 20 was the answer for some time, but no one had run through the starting positions to prove it.

[Team member Morley] Davidson said this was “pure religion” as no-one had managed to crunch their way through all configurations. “We were secretly hoping in our tests that there would be one that required 21,” he said. [BBC]

Still, the researchers suggest, don’t expect the confidence boost of a known 20-move maximum to help you solve the Cube any faster.

There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves. [Team website]

Related content:
80beats: Has the Devilish Math Problem “P vs NP” Finally Been Solved?
80beats: Brilliant & Reclusive Russian Mathematician Doesn’t Need Your Prize Money
80beats: Can a Google Algorithm Predict Nobel Prize Winners?
Discoblog: Book-Balancing, Rubik’s Cube-Solving, Pi-Reciting Geek Girl Goes Viral
Discoblog: A Rubik’s Cube Could Tell Us Which Arm Is an Octopus’ Favorite

Image: flickr / kirtaph