Wednesday, August 11, 2010

ஐ God's Number is 20 ஐ


Every position of Rubik's Cube™ can be solved in twenty moves or less.
With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves.
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.
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.



DateLower boundUpper boundGapNotes and Links
July, 1981185234Morwen Thistlethwaite proves 52 moves suffice.
April, 1992184224Hans Kloosterman improves this to 42 moves.
May, 1992183921Michael Reid shows 39 moves is always sufficient.
May, 1992183719Dik Winter lowers this to 37 moves just one day later!
January, 1995182911Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm.
January, 199520299Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.
December, 200520288Silviu Radu shows that 28 moves is always enough.
April, 200620277Silviu Radu improves his bound to 27 moves.
May, 200720266Dan Kunkle and Gene Cooperman prove 26 moves suffice.
March, 200820255Tomas Rokicki cuts the upper bound to 25 moves.
April, 200820233Tomas Rokicki and John Welborn reduce it to only 23 moves.
August, 200820222Tomas Rokicki and John Welborn continue down to 22 moves.
July, 201020200Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki prove that God's Number for the Cube is exactly 20.

No comments:

Post a Comment