Today I found out that all 43,252,003,274,489,856,000 positions of a standard Rubik’s Cube can be solved in 20 moves or less.

Anyone who is serious about solving a Rubik’s Cube uses some sort of algorithm, or sequence of steps to help them solve the puzzle. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized and used by a human typically require more than forty moves.  It turns out though, this number is a bit high, in terms of actually using the most efficient solution for a given position on a standard Rubik’s Cube. This was proved in July of 2010 by Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge who used 35 “CPU years”* worth of computing time, donated by Google, to prove that one only needs a maximum of 20 moves to solve any position on a standard Rubik’s Cube.

Interestingly, the researchers did not solve every position by its optimal solution.  Rather, once they discovered one position that definitely needed 20 moves to solve in the most efficient manner, they then did not try to solve the other positions for their optimal solution.  They only required that it be solved in 20 moves or less, to make sure it was below the now known upper bound.  As long as all the other positions could be solved in under this amount, they knew this number had to be the upper bound on moves needed to solve any position on the standard Rubik’s Cube.  The benefit to doing it this way was that it drastically decreased the number of calculations required to prove that no position on the standard Rubik’s Cube needed more than 20 moves to solve.

*note:  One “CPU Year” is typically referred to as the work potential able to be done by one Giga-FLOP machine in one year.  For those who aren’t familiar, a “FLOP” just means “Floating Point Operations Per Second”. Thus, a one FLOP machine can do one operation per second.  A one Giga-FLOP machine, usually abbreviated as a GFLOP, can do one billion operations per second.  So to prove the above, the researchers used 35 CPU Years or around 1,103,760,000,000,000,000 operations, which, you’ll note, is less than the number of possible Rubik’s Cube positions.  For more on how exactly they managed to reduce the problem so drastically to be able to do it in so “few” operations, click here.

Bonus Facts:

• The standard Rubik’s Cube has 26 cubes with inward extensions that interlock together with the other cubes.  The center cube of each of the six sides is locked to the core mechanism within the cube, providing a base structure for the other pieces.
• The easiest way to “solve” a Rubik’s Cube is simply to take it apart and re-arrange the cubes such that it is solved when put back together. Moving the stickers works too, but carries the potential of tearing the stickers and making the cheating obvious.  🙂
• The Rubik’s Cube was invented in 1974 by a Hungarian professor of architecture, Ernő Rubik. Originally, he was toying around and attached several blocks together with a rubber band. In this original system, after several twists, the rubber band broke.  He then became interested in the structural problem of how to move the blocks independently for an arbitrary number of turns without the cube falling apart.  Interestingly, he had not actually intended to create a puzzle when he designed this.  Rather, he was more interested in solving the structural problem of creating the cube itself.  Shortly after its invention, in 1975, he applied for and was granted Hungarian patent HU170062, where his “magic cube” was first marketed.
• The puzzle was licensed by Rubik to be sold by Ideal Toy Corp, in 1980. Because Rubik had not met the requirements to be able to file an international patent in the time scale required, it allowed anyone to manufacture and sell one of these “magic cubes” outside of Hungary.  To help get around this problem somewhat, Ideal Toy Corp changed the name to the more memorable and trademarkable “Rubik’s Cube”, rather than sticking with the generic “Magic Cube” name.  Rubik himself was eventually granted patents for the Rubik’s Cube in a variety of countries, such as the United States in 1983.
• The Rubik’s cube was also independently invented by a self-taught engineer, Terutoshi Ishigi, in Japan in 1976.  His cube was almost exactly like Rubik’s cube inside and out, though he knew nothing of that, having invented his cube around the same time as Rubik.  Rubik is credited as the inventor though, because Ishigi didn’t receive his patent (in Japan) until about a year after Rubik in Hungary.
• As of January 2009, 350 million cubes have been sold worldwide.
• Speedcubing is the practice of trying to solve a Rubik’s Cube in the shortest time possible.  The first world championship organized by the Guinness Book of World Records was held in Munich on March 13, 1981.
• The current world record on a 3×3×3 Rubik’s Cube was set by Feliks Zemdegs, who had a best time of 5.66 seconds at the Melbourne Winter Open 2011.
• If you took one turn of a Rubik’s Cube face very second, it would take you 1,400 million years to go through all the possible cube configurations.
• In 1981, Frau Schmit of Dusseldorf Germany sued her husband for divorce, citing the Rubik’s Cube as co-respondent. She stated “Gunder no longer speaks to me and when he comes to bed he is too exhausted from playing with his cube to even give me a cuddle.”
• The most expensive Rubik’s Cube ever made is the “Master Cube” created by Diamond Cutters International in 1995. This standard size, fully functional cube has 22.5 carats of amethyst, 34 carats of rubies, and 34 carats of emeralds, all set in 18 carat gold and is worth an estimated 1.5 million dollars.