God's Number Is 20

A few years ago, Slashdot reported that a Rubik's Cube could be solved in 23 moves. That's hardly impressive, now that the number has been whittled down to just 20. Of course to prove that, it took 35 years of computer time (donated by Google, who had the juice to get it done)

Boastfully, Cube20.org states:

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.

What is interesting is how the number has dwindled over time. By 1981, an upper boundary of 52 moves had been confirmed, but the next jump took over a decade, where the gap closed by 10 moves. By 1995, the upper limit was just below thirty, but it would take another decade before they could confirm movement down to 28. And since then they made incredible progress to lock in 20.

Still wondering how they solved all 43,252,003,274,489,856,000 positions of the Cube? Check it out in nerdglorious detail.