Rubik's Cube quest for speedy solution comes to an end

A 30-year quest to find the minimum number of moves needed to solve every one of the billions of configurations for a Rubik's Cube may have ended. Any scrambled cube can be solved in 20 moves or fewer, researchers claim. The international team used a bank of computers at Google to help crank through the solutions.

The figure is known as "God's number" because an all-knowing entity would know the optimal number of steps needed to solve the puzzle. "We now know for certain that the magic number is 20," Professor Morley Davidson, a mathematician from Kent State University, told BBC News.

The results suggest that there are more than 100,000 starting positions - of a possible 43 billion - that can be solved in exactly 20 moves. However, the majority of solutions take between 15 and 19 moves to solve.

Until 1995 researchers thought that the theoretical minimum number of moves to solve the classic puzzle was 18. Work by mathematician Michael Reid revised the figure to 20 after the discovery of a configuration that could not be cracked in fewer moves.

However, Prof Davidson said that the number 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.

To crunch their way through all of the possible combinations of a Rubik's Cube, the researchers split all of the possibilities into 2.2 billion groups, known as cosets, each containing 20 billion positions.

Prof Davidson said that it would have been "completely hopeless" to try to compute all of the groups. So, to make it more manageable, they reduced it by spotting duplicates and using symmetry to spot other similar combinations.

The team eventually managed to reduce the number to 56 million sets of 20 billion combinations. Each coset would take a "good PC 20 to 30 seconds to sort", said Prof Davidson, meaning it would take a huge amount of time to compute with a standard desktop PC.

As a result, the team had planned to process the batches on a supercomputer. "Then Google stepped forward and offered to run the computation," he said. "We still don't know what machinery they used."

At the end of the exercise, Prof Davidson and his team said they were convinced the problem had been cracked and that God's number for the Rubik's Cube was 20.

"It's come full circle for me," he said. "Rubik's Cube was an icon of the 80s when I was growing up and was the reason I went into mathematics."