Feeds

Google, boffins crack Rubik's Cube mystery

The ultimate answer - or is it?

Providing a secure and efficient Helpdesk

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

Internet Security Threat Report 2014

More from The Register

next story
MARS NEEDS WOMEN, claims NASA pseudo 'naut: They eat less
'Some might find this idea offensive' boffin admits
LOHAN crash lands on CNN
Overflies Die Welt en route to lively US news vid
Comet Siding Spring revealed as flying molehill
Hiding from this space pimple isn't going to do humanity's reputation any good
Experts brand LOHAN's squeaky-clean box
Phytosanitary treatment renders Vulture 2 crate fit for export
No sail: NASA spikes Sunjammer
'Solar sail' demonstrator project binned
Carry On Cosmonaut: Willful Child is a poor taste Star Trek parody
Cringeworthy, crude and crass jokes abound in Steven Erikson’s sci-fi debut
Origins of SEXUAL INTERCOURSE fished out of SCOTTISH LAKE
Fossil find proves it first happened 385 million years ago
Human spacecraft dodge COMET CHUNKS pelting off Mars
Odyssey orbiter yet to report, though - comet's trailing trash poses new threat
prev story

Whitepapers

Forging a new future with identity relationship management
Learn about ForgeRock's next generation IRM platform and how it is designed to empower CEOS's and enterprises to engage with consumers.
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.
Three 1TB solid state scorchers up for grabs
Big SSDs can be expensive but think big and think free because you could be the lucky winner of one of three 1TB Samsung SSD 840 EVO drives that we’re giving away worth over £300 apiece.
Reg Reader Research: SaaS based Email and Office Productivity Tools
Read this Reg reader report which provides advice and guidance for SMBs towards the use of SaaS based email and Office productivity tools.
Security for virtualized datacentres
Legacy security solutions are inefficient due to the architectural differences between physical and virtual environments.