London: A team of experts has finally found the answer to a long-standing question: How many moves does it take to solve a Rubik Cube?
A maximum of 20 moves is all it takes, according to a new study.
With the help of Google to check all 43 quintillion possible jumbled positions the cube can take, the team has finally arrived at this number.
"The primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate," New Scientist quoted Tomas Rokicki, a programmer from Palo Alto, California, as saying.
The figure is dubbed "God’s number", the assumption being that even the Almighty couldn’t solve the puzzle faster.
Previous methods solved around 4000 cubes per second by attempting a set of starting moves, then determining if the resulting position is closer to the solution. If not, the algorithm throws those moves away and starts again.
Rokicki`s key insight was to realise that these dead-end moves are actually solutions to a different starting position, which led him to an algorithm that could try out one billion cubes per second.
We’ve known for 15 years that some configurations of the cube require just 20 moves to solve – and many mathematicians suspected that none needed more. The team’s exhaustive search proves them right
"Research like this shows how pure mathematics can often be used to make hard computational problems more feasible," says Mark Kambites, a mathematician at the University of Manchester.
"The Rubik’s cube is an interesting test case for the methods of computational group theory," he added.
The study is published in The Mathematical Intelligencer.