|Photo credit: ToniBlay/Flickr|
Researchers have spent 30 years trying to unlock the secrets of the Rubik's Cube, testing algorithms and documenting sequences. Using about 35 CPU-years of idle computer time donated by Google, a new study has shown that from any starting position, the Rubik's Cube can be solved in twenty, yes twenty, moves or less.
The full explanation involves lots of numbers and equations and all 43,252,003,274,489,856,000 positions of the Cube, but here are the findings in part:
"Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube. One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves.So next time you're turning and twisting for the 400th time, just keep reminding yourself that the solution is only twenty moves away—unbelievable!
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.
It took fifteen years after the introduction of the Cube to find the first position that provably requires twenty moves to solve; it is appropriate that fifteen years after that, we prove that twenty moves suffice for all positions."
|ShareThis | Posted August 11, 2010 at 11:22 PM|
You can leave a response, or trackback from your own site.