Feeds

Google, boffins crack Rubik's Cube mystery

The ultimate answer - or is it?

5 things you didn’t know about cloud backup

Has Google finally cracked it? Revealed today, courtesy of the massed ranks of Google computing, the answer to the ultimate question – not the old one about Life the Universe and Everything – is 20!

We’re talking God’s Number here, or more prosaically the maximum number of moves required to solve the Rubik's Cube no matter what the start position. This result, if no one comes up with a position that demands 21 moves or more, is the end of a 30 year quest that began in July 1981 with a claim by mathematician Morwen B Thistlethwaite that 52 was the answer.

That stuck for just over 11 years, until in August 1992 Hans Kloosterman claimed he had proof that it was indeed 42. In the course of the two decades that followed, scientists and mathematicians with time on their hands gradually whittled that number down until, in August 2008, a group including one Tomas Rokicki decided that 22 might be the answer.

It wasn’t, and Mr Rokicki, who had also been responsible for the previous two estimates of this number, now got together with a team that included John Dethridge, Herbert Kociemba and Professor Morley Davidson, a mathematician from Kent State University.

In order to work through all possible combinations of a Rubik's Cube, the team then split all of the possibilities into 2.2 billion groups, known as cosets, each containing 20 billion positions.

Prof Davidson told the BBC that it would have been "completely hopeless" to try to compute all of the groups. They therefore reduced the task by spotting duplicates and using symmetry to identify other similar combinations, managing eventually to reduce the number to 56 million sets of 20 billion combinations.

At an optimistic 20 seconds per coset, this would have taken a reasonable PC the best part of seven months to solve, and the team started to look around for a supercomputer to carry out the processing for them. At this point, Google stepped forward and offered to run the computation.

Good news? Probably, although Professor Morley told the Beeb: "We still don't know what machinery they used."

Nonetheless, as the exercise went on, the probability of there being a combination which required more than 20 moves to solve "dropped into the very low digits". By the end of the exercise, Davidson and his team declared the problem well and truly cracked and that God's Number for the Rubik's Cube was definitely 20.

This result will now be sent out to a mathematical journal for peer review.

Good news, too, for Rokicki, who can now get back to his favourite pastimes, which include programming cellular automata (golly) and the Propeller microcontroller.

Bootnote

How many mathematicians does it take to screw in a light bulb? In earlier work, it has been shown that one mathematician can change a light bulb. Now, f {k} mathematicians can change a light bulb, and if one more simply watches them do it, then {k+1} mathematicians will have changed the light bulb.

Therefore, by induction, for all n in the positive integers, n mathematicians can change a light bulb. ®

Secure remote control for conventional and virtual desktops

More from The Register

next story
Boffins attempt to prove the UNIVERSE IS JUST A HOLOGRAM
Is this the real life? Is this just fantasy?
Our LOHAN spaceplane ballocket Kickstarter climbs through £8000
Through 25 per cent but more is needed: Get your UNIQUE rewards!
Software bug caught Galileo sats in landslide, no escape from reality
Life had just begun, code error means Russia's gone and thrown it all away
LOHAN tunes into ultra long range radio
And verily, Vultures shall speak status unto distant receivers
SpaceX prototype rocket EXPLODES over Texas. 'Tricky' biz, says Elon Musk
No injuries or near injuries. Flight stayed in designated area
Galileo, Galileo! Galileo, Galileo! Galileo fit to go. Magnifico
I'm just a poor boy, nobody loves me. But at least I can find my way with ESA GPS by 2017
EOS, Lockheed to track space junk from Oz
WA facility gets laser-eyes out of the fog
prev story

Whitepapers

Gartner critical capabilities for enterprise endpoint backup
Learn why inSync received the highest overall rating from Druva and is the top choice for the mobile workforce.
Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
Rethinking backup and recovery in the modern data center
Combining intelligence, operational analytics, and automation to enable efficient, data-driven IT organizations using the HP ABR approach.
Consolidation: The Foundation for IT Business Transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.
Next gen security for virtualised datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.