The world has waited with bated breath for three decades, and now finally a group of academics, engineers, and math geeks have finally found the magic number. That number is 20, and it's the maximum number of moves it takes to solve a Rubik's Cube.
Known as "God's Number", the magic number required about 35 CPUyears and a good deal of manhours to solve. Why? Because there's 43,252,003,274,489,856,000 possible positions of the cube, and the computer algorithm that finally cracked God's Algorithm had to solve them all. (The terms "God's Number/Algorithm are derived from the fact that if God was solving a Cube, he/she/it would always do it in the most efficient way possible.)
A full breakdown of the history of God's Number as well as a full breakdown of the math is available here, but summarily the team broke the possible positions down into sets, then drastically cut the number of possible positions they had to solve for through symmetry (if you scramble a Cube randomly and then turn it upside down, you haven't changed the solution).
They then borrowed some computing time from Google (one of the principals is an engineer there) and burned about 35 coreyears to solve all the possible positions. The number 20 has been the lower limit for God's Number for more than a decade, but the team was finally able to whittle away at the upper limit (which was trimmed back to 22 in 2008).
So far the algorithm has identified some 12 million distance20 positions, though there are definitely many more than that. Click on this link if you want to see what some of the hardest positions are, and how they exactly tackled this problem.
Source: PopSci
