Rubik's Cube quest for speedy solution comes to an end

Rubik's Cube The Rubik's Cube was invented in 1974 by a Hungarian architect called Erno Rubik

Related Stories

A 30-year quest to find the fewest number of moves needed to solve any one of the billions of configurations for a Rubik's Cube may have ended.

Any scrambled puzzle can be solved in 20 moves or fewer, researchers claim.

The international team used a bank of computers at Google to help crank through the solutions.

The figure is known as "God's number" because an all-knowing entity would know the optimal number of steps needed to solve the puzzle.

"We now know for certain that the magic number is 20," Professor Morley Davidson, a mathematician from Kent State University, told BBC News.

The results suggest that there are more than 100 million starting positions - of a possible 43 billion billion - that can be solved in exactly 20 moves.

However, the majority of solutions take between 15 and 19 moves to solve.

'Hopeless problem'

Until 1995 researchers thought that the theoretical minimum number of moves to solve the classic puzzle was at least 18 for many positions. Work by mathematician Michael Reid revised the figure to 20 after the discovery of a configuration that could not be cracked in fewer moves.

However, Prof Davidson said that the popular notion that 20 was also the maximum remained. He said this was "pure religion" as no-one had managed to crunch their way through all configurations.

"We were secretly hoping in our tests that there would be one that required 21," he said.

Start Quote

Rubik's Cube was an icon of the 80s when I was growing up and was the reason I went into mathematics”

End Quote Prof Davidson

To crunch their way through all of the possible combinations of a Rubik's Cube, the researchers split all of the possibilities into 2.2 billion groups, known as cosets, each containing 20 billion positions.

Prof Davidson said that it would have been "completely hopeless" to try to compute all of the groups. So, to make it more manageable, they reduced it by spotting duplicates and using symmetry to spot other similar combinations.

The team eventually managed to reduce the number to 56 million sets of 20 billion combinations.

Each coset would take a "good PC 20 to 30 seconds to sort", said Prof Davidson, meaning it would take a huge amount of time to compute with a standard desktop PC.

As a result, the team had planned to process the batches on a supercomputer.

"Then Google stepped forward and offered to run the computation," he said.

"We still don't know what machinery they used."

Code check

In the first of two phases, the computers were used to crank through as many combinations as possible. However, some still "slipped through the cracks" and required slower desktop software to solve.

As the exercise went on, he said, the probability of there being a combination which required more than 20 moves to solve "dropped into the very low digits".

Rubik's Cube

  • Invented in 1974 by Hungarian architect Erno Rubik
  • Around 400m sold to date
  • Fastest human 'solve' in 7.08 seconds by Erik Akkersdijk

At the end of the exercise, Prof Davidson and his team said they were convinced the problem had been cracked and that God's number for the Rubik's Cube was 20.

"It's come full circle for me," he said. "Rubik's Cube was an icon of the 80s when I was growing up and was the reason I went into mathematics."

The initial results have already been published online and Prof Davidson said they would now be submitted to peer-reviewed journals.

"People are welcome to verify the code," he said.

However, he said, the team may not be done with the Rubik's Cube just yet.

They might now turn their attention to the four-layered version or could attack other mathematical problems related to the classic cube.

"It's the universal popularity of the puzzle - it's probably the most popular puzzle in human history."

The work was carried out with John Dethridge, an engineer at Google, Herbert Kociemba, a maths teacher and Tomas Rokicki, a programmer from California.

More on This Story

Related Stories

The BBC is not responsible for the content of external Internet sites

More Technology stories

RSS

Features

  • Peaky Blinders publicity shotBrum do

    Why is the Birmingham accent so difficult to mimic?


  • Oliver CromwellA brief history

    The 900-year-story behind the creation of a UK parliament


  • Image of Ankor Wat using lidarJungle Atlantis

    How lasers have revealed an ancient city beneath the forest


  • TigerBard taste? Watch

    Are trailer videos on social media spoiling theatre?


  • Tesco signBest before?

    Has Tesco passed its sell-by date, asks Richard Anderson


BBC © 2014 The BBC is not responsible for the content of external sites. Read more.

This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.