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

Next gen security for virtualised datacentres

More from The Register

next story
Vulture 2 takes a battering in 100km/h test run
Still in one piece, but we're going to need MORE POWER
TRIANGULAR orbits will help Rosetta to get up close with Comet 67P
Probe will be just 10km from Space Duck in October
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
China to test recoverable moon orbiter
I'll have some rocks and a moon cheese pizza please, home delivery
What does a flashmob of 1,024 robots look like? Just like this
Sorry, Harvard, did you say kilobots or KILLER BOTS?
NASA's rock'n'roll shock: ROLLING STONE FOUND ON MARS
No sign of Ziggy Stardust and his band
Why your mum was WRONG about whiffy tattooed people
They're a future source of RENEWABLE ENERGY
Vulture 2 spaceplane autopilot brain surgery a total success
LOHAN slips into some sexy bespoke mission parameters
prev story

Whitepapers

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.
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.
Build a business case: developing custom apps
Learn how to maximize the value of custom applications by accelerating and simplifying their development.
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.
Next gen security for virtualised datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.