💾 Archived View for gmi.noulin.net › mobileNews › 2217.gmi captured on 2024-05-10 at 13:20:39. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
2010-08-12 09:13:31
By Jonathan Fildes Technology reporter, BBC News
A 30-year quest to find the fewest number of moves needed to solve any one of the billions of configurations for a Rubik's Cube may have ended.
Any scrambled puzzle 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 million starting positions - of a possible 43 billion billion - that can be solved in exactly 20 moves.
However, the majority of solutions take between 15 and 19 moves to solve.
'Hopeless problem'
Until 1995 researchers thought that the theoretical minimum number of moves to solve the classic puzzle was at least 18 for many positions. 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 popular notion that 20 was also the maximum remained. He 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.
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."
Code check
In the first of two phases, the computers were used to crank through as many combinations as possible. However, some still "slipped through the cracks" and required slower desktop software to solve.
As the exercise went on, he said, the probability of there being a combination which required more than 20 moves to solve "dropped into the very low digits".
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."
The initial results have already been published online and Prof Davidson said they would now be submitted to peer-reviewed journals.
"People are welcome to verify the code," he said.
However, he said, the team may not be done with the Rubik's Cube just yet.
They might now turn their attention to the four-layered version or could attack other mathematical problems related to the classic cube.
"It's the universal popularity of the puzzle - it's probably the most popular puzzle in human history."
The work was carried out with John Dethridge, an engineer at Google, Herbert Kociemba, a maths teacher and Tomas Rokicki, a programmer from California.