Google help to solve Rubik's Cube 'God Number'

A team of researchers, including a Google engineer, has produced a proof that shows that no initial Rubik's Cube position needs over 20 moves to solve.

Prior to this, researchers had narrowed down the lower bound of the number to 20 and the upper bound to 22. The figure is called 'God's Number' because it is the highest number of moves that a perfect, all-knowing (omniscient) entity would have to go through to reach a solution in any given arrangement.

To help solve the puzzle, Google donated over 35 CPU-years of idle computer time to the project. Google does not release information on its computer systems, but the site that has been used to announce the solution says that "it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation."

A Rubik's Cube has 43,252,003,274,489,856,000 potential positions. This proof shows that any of these states are no more than 20 moves away from being solved and the majority of solutions take between 15 and 19 moves to solve. There are only around 300,000,000 positions that are so complex as to require 20 moves to reach a solution.

Google had not responded with clarification of their precise involvement at the time of writing.

For mathematically curious ZDNet UK readers, reddit's comment pages are a mine of information on the subject.