Google Helps Find Simplest Solution to Rubik’s Cube

August 17, 2010

Any Rubik’s Cube can be solved in 20 moves or less, according to a team of mathematicians and programmers.

In order to arrive at this number, Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki examined all 43,252,003,274,489,856,000 possible positions of the Cube via a complex (and secret) computer operation. The research team used a computer donated by Google to run complex algorithms for their study.

“It took 15 years after the introduction of the Cube to find the first position that provably requires 20 moves to solve,” according to the team’s website. “It is appropriate that 15 years after that, we prove that 20 moves suffice for all positions.”

The shortest number of moves by the most efficient algorithm is called “God’s number.” Thirty years ago, it was thought that a minimum of 52 moves was required. In mid-2007, it was 26. By mid-2008, it had been reduced to 22.

In related news, the official speed record for solving the puzzle is 7.08 seconds, established in 2008.

Source: Wired (August 15, 2010)