Most Rubik’s cube enthusiasts would probably know this for quite some time now, but I can’t resist the urge to share this fact: Every possible configuration of the Rubik’s cube can be solved in at most 20 moves.

The tediousness involved in finding this number, coined as the elusive God’s number, has stumped a lot of computer scientists and mathematicians since 1974, the year when the twisty puzzle was created by Ernő Rubik. To realize the mathematical rigor required to achieve this feat, consider the 43,252,003,274,489,856,000 or ~43 quintillion possible permutations of the cube. To put this into perspective, if one had as many 57-millimeter Rubik’s Cubes as there are permutations, one could cover the Earth’s surface with a layer 275 cubes thick!

The problem of finding the exact God’s number was relaxed by solving first its lower and upper bounds , hoping that the gap will close to a certain integer at a later time. The lower bound is generally created by finding at least one configuration that required no less than a that number of moves while the upper bound is mathematically proven or an algorithm/heuristic is invented, both tested with the help of computers. Needless to say, a divide-and-conquer approach was applied to most algorithms.

Key events:

  • On July 1981, the first ever published attempt was made by Morwen Thistlethwaite, one the many methods that would soon be used in the Fewest Moves category of official Rubik’s cube competitions. He pegged the bounds of God’s number to be between 18 to 52 moves.
  • Using his observations from Thistlethwaite’s four-phase algorithm, Herbert Kociemba made a two-phase algorithm instead, the first phase effectively replacing the first two steps of Thistlethwaite’s and the second phase for the remaining two steps. Note that this algorithm would unknowingly be the algorithm to find God’s number. The time gap between this algorithm and the mathematical proof is largely due to lack of computer processing power.
  • On January 1995, Michael Reid used Kociemba’s algorithm to significantly reduce the upper bound from 37 to 29.
  • By the same month, Reid mathematically proved that the “superflip” configuration, i.e. all pieces are in correct positions, except that edges are flipped, required no less than 20 moves, effectively making the range for God’s number to be 20-29.

    The "superflip" configuration

  • It would take almost 11 years (December 2005) to reduce the upper bound by 1 move (28). After this year, the commodification of better processing power largely helped in reducing the upper bound 1 move per intervals of between a month to almost two years.
  • Finally on July 2010, with the help of Google (donating 35 CPU-years* of idle computer time), the gap was closed at 20 in just a few weeks by Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge

Explaining the solution in detail may not be suitable for the average reader as it involves group theory (higher-level algebra), and I, being a Mathematics graduate, can only partially understand the mathematical rigor involved. Instead, consider this analogous situation:

Let each of the ~43 quintillion configurations be a huge lump of different kinds of fruit instead (duplicates are possible, assume sizes are equal, and each fruit of the same kind only differ in taste, nutrients, etc.). Separate each fruit into a different basket according to its kind. The question to be answered now is how many bites it takes you to finish a fruit. The good solution would like be to take one fruit from each basket instead of eating everything. A faster solution is to share all these fruits with other people of the same bite-size.

After 30 years, geeks have now conquered the 3x3x3 cube. The question now is: what’s next? 4x4x4? 5x5x5? … nxnxn? So far, the largest patented cube is 12x12x12, and there is a wide variety of twisty puzzles that are more challenging than the Rubik’s cube. There are even 100x100x100, 4D, 5D cubes to solve (search them in google)!

Meanwhile, the wide majority are still trying to solve one color, reattaching the stickers, or reassembling it.

As for me, I’m back to around 40 seconds per solve ’cause it’s been a long time since I practiced seriously. To see the difference, look at my performance 2 years ago:

——-

*CPU-year = the number of years a good desktop PC can solve such a problem by itself. By 2010, a “good desktop PC” is an Intel Nehalem, four-core, 2.8GHz.

Source: http://cube20.org/

Advertisements