Rubik's cube mystery solved after 15 years

Rubik's cube mystery solved after 15 years - New Scientist

It has taken 15 years to get to this point, but it is now clear that every possible scrambled arrangement of the Rubik's cube can be solved in a maximum of 20 moves – and you don't even have to take the stickers off.

That's according to a team who combined the computing might of Google with some clever mathematical insights to check all 43 quintillion possible jumbled positions the cube can take. Their feat solves the biggest remaining puzzle presented by the Rubik's cube.

"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.

The figure is dubbed "God's number", the assumption being that even the Almighty couldn't solve the puzzle faster. New Scientist reported in 2008 that Rokicki had reduced the value of God's Number to 22, but it was clear that bringing it down further would require some clever shortcuts.

Exploiting symmetry

To further simplify the problem, Rokicki and his team have now used techniques from the branch of mathematics called group theory .

First they divided the set of all possible starting configurations into 2.2 billion sets, each containing 19.5 billion configurations, according to how these configurations respond to a group of 10 possible moves.

This grouping allowed the team to reduce the number of sets to just 56 million, by exploiting various symmetries of a cube. For example, turning a scrambled cube upside down doesn't make it harder to solve, so these equivalent positions can be ignored.

That still left a vast number of starting configurations to check, however, so the team also developed an algorithm that speeds up this process.