Washington

WASHINGTON (AFP) – 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 besolved 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 that its jaunty colorsmight 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 color-aligned solution.

"Everysolver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube," said the team of mathematicians, who include Morley Davidson of Ohio's Kent State University, Google engineerJohn Dethridge, German math teacher Herbert Kociemba and Tomas Rokicki, a California programmer.
"There are many different algorithms, varying in complexity and number of moves required, but thosethat can be memorized by a mortal typically require more than forty moves."
One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this isknown 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 colored cubes that make up Erno Rubrik's 1974 invention.
"It took fifteen years after the introduction of the Cube to findthe first position that provably requires 20 moves to solve," the team said. "It is appropriate that fifteen years after that, we prove that twenty moves suffice for all position."
Using computers lentto them by Google -- the company won't 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...