It has taken 15 years to get to this point, but it is now clear that every possible scrambled arrangement of the Rubik鈥檚 cube can be solved in a maximum of 鈥� and you don鈥檛 even have to take the stickers off.
That鈥檚 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鈥檚 cube.
鈥淭he primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate,鈥� says , 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鈥檚 cube.
Advertisement
The figure is dubbed 鈥淕od鈥檚 number鈥�, the assumption being that even the Almighty couldn鈥檛 solve the puzzle faster. New 杏吧原创 reported in 2008 that Rokicki had reduced the value of God鈥檚 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鈥檛 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.
Useful dead ends
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鈥檚 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.
You can think of his solution like this. Imagine visiting a friend in an unfamiliar city. They鈥檝e given you directions indicating when to turn left or right, but neglected to include a starting point. If you follow the directions from a random point it鈥檚 unlikely you鈥檒l reach your destination, but matching them to the right starting point will definitely get you there.
Similarly, the team鈥檚 algorithm rapidly matches moves to the correct starting point, allowing them to solve each set of 19.5 billion in under 20 seconds.
Computing empire
Even at this speed, completing the entire task would take around 35 years on an ordinary computer. So the team鈥檚 solution relies on another shortcut: John Dethridge, an engineer at Google in Mountain View, California, was able to use his employers鈥� vast computing empire to solve the problem in a matter of weeks.
We鈥檝e 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鈥檚 exhaustive search proves them right
鈥淩esearch like this shows how pure mathematics can often be used to make hard computational problems more feasible,鈥� says , a mathematician at the University of Manchester who was not involved in the team鈥檚 work. 鈥淭he Rubik鈥檚 cube is an interesting test case for the methods of computational group theory.鈥�
The work has not yet been peer reviewed but Rokicki points out that it is an extension of that was published in The Mathematical Intelligencer, which reduced God鈥檚 number to 22.
