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

Summary: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.

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.

Topics: Storage

About

Jack Clark has spent the past three years writing about the technical and economic principles that are driving the shift to cloud computing. He's visited data centers on two continents, quizzed senior engineers from Google, Intel and Facebook on the technologies they work on and read more technical papers than you care to name on topics f... Full Bio

Kick off your day with ZDNet's daily email newsletter. It's the freshest tech news and opinion, served hot. Get it.

Related Stories

The best of ZDNet, delivered

You have been successfully signed up. To sign up for more newsletters or to manage your account, visit the Newsletter Subscription Center.
Subscription failed.