The magic Rubik's number revealed
WASHINGTON // An international team of researchers using computer time lent to them by Google has found every way the popular Rubik's Cube puzzle can be solved, and showed it can always be solved in 20 moves or less. The study is just the latest attempt by Rubik's enthusiasts to figure out the secrets of the cube, which has proven to be altogether far more complicated than its jaunty colours might suggest.
At the crux of the quest has been a bid to determine the lowest number of moves required to get the cube from any given muddled configuration to the colour-aligned solution. "Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube," said the team of mathematicians, which included Morley Davidson of Ohio's Kent State University, the Google engineer John Dethridge, the German maths teacher Herbert Kociemba and the California programmer Tomas Rokicki.
"There are many different algorithms, varying in complexity and number of moves required, but those that can be memorised by a mortal typically require more than 40 moves." "One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God's Algorithm. The number of moves this algorithm would take in the worst case is called God's Number. At long last, God's Number has been shown to be 20."
The research, published online, ends a 30-year search for the most efficient way to correctly align the 26 coloured cubes that make up Erno Rubik's 1974 invention. "It took 15 years after the introduction of the Cube to find the first position that provably requires 20 moves to solve," the team said. "It is appropriate that 15 years after that, we prove that 20 moves suffice for all positions." Using computers lent to them by Google - the company will not disclose how many or how powerful they are - the team crunched through billions of Cube positions, solving each one over a period of "just a few weeks."
The study builds on the work of a veritable pantheon of Rubik's researchers, starting with Morwen Thistlethwaite, who in 1981 showed 52 moves were sufficient to reach the solution from any given Cube position. By May 1992, Michael Reid showed 39 moves were always sufficient, only to be undercut a mere day later by Dik Winter, who showed 37 moves would work. * Agence France-Presse
Published: August 15, 2010 04:00 AM