Feeds

Google, boffins crack Rubik's Cube mystery

The ultimate answer - or is it?

Secure remote control for conventional and virtual desktops

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. ®

Boost IT visibility and business value

More from The Register

next story
Our LOHAN spaceplane ballocket Kickstarter climbs through £8000
Through 25 per cent but more is needed: Get your UNIQUE rewards!
Cutting cancer rates: Data, models and a happy ending?
How surgery might be making cancer prognoses worse
Boffins ID freakish spine-smothered prehistoric critter: The CLAW gave it away
Bizarre-looking creature actually related to velvet worms
CRR-CRRRK, beep, beep: Mars space truck backs out of slippery sand trap
Curiosity finds new drilling target after course correction
SpaceX prototype rocket EXPLODES over Texas. 'Tricky' biz, says Elon Musk
No injuries or near injuries. Flight stayed in designated area
Brit balloon bod Bodnar overflies North Pole
B-64 amateur ultralight payload approaching second circumnavigation
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
Astronomers scramble for obs on new comet
Amateur gets fifth confirmed discovery
prev story

Whitepapers

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.
5 things you didn’t know about cloud backup
IT departments are embracing cloud backup, but there’s a lot you need to know before choosing a service provider. Learn all the critical things you need to know.
Why and how to choose the right cloud vendor
The benefits of cloud-based storage in your processes. Eliminate onsite, disk-based backup and archiving in favor of cloud-based data protection.
Top 8 considerations to enable and simplify mobility
In this whitepaper learn how to successfully add mobile capabilities simply and cost effectively.
High Performance for All
While HPC is not new, it has traditionally been seen as a specialist area – is it now geared up to meet more mainstream requirements?