PALO ALTO, Calif., Aug. 11 (UPI) — U.S. mathematicians say they’ve solved the riddle of the minimum number of moves it takes to solve the Rubik’s Cube puzzle, a figure they call “God’s number.”
A team from Palo Alto, Calif., says every possible scrambled arrangement of the puzzle can be solved in no more than 20 moves, NewScientist.com reported Wednesday.
They combined computing power with mathematical insights to check all 43 quintillion possible jumbled positions the cube can take, says Tomas Rokicki, a programmer who has spent 15 years looking for the least number of moves guaranteed to solve any configuration of the Rubik’s cube.
“The primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate,” Rokicki says.
Previous computer methods solved around 4,000 possible cubes a second by attempting a set of starting moves, then determining if the resulting position was closer to the solution. If not, the computer would throw out those moves and start again.
Rokicki’s key insight was to realize these dead-end moves are actually solutions to a different starting position, which led him to a computer algorithm that could try out 1 billion cubes per second.
The team has dubbed the 20-moves solution “God’s number,” the assumption being that even the Almighty couldn’t solve the puzzle faster, NewScientist said.
Copyright 2010 United Press International, Inc. (UPI). Any reproduction, republication, redistribution and/or modification of any UPI content is expressly prohibited without UPI’s prior written consent.