Feeds

Google, boffins crack Rubik's Cube mystery

The ultimate answer - or is it?

Intelligent flash storage arrays

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

Providing a secure and efficient Helpdesk

More from The Register

next story
SECRET U.S. 'SPACE WARPLANE' set to return from SPY MISSION
Robot minishuttle X-37B returns after almost 2 years in orbit
No sail: NASA spikes Sunjammer
'Solar sail' demonstrator project binned
LOHAN crash lands on CNN
Overflies Die Welt en route to lively US news vid
You can crunch it all you like, but the answer is NOT always in the data
Hear that, 'data journalists'? Our analytics prof holds forth
Experts brand LOHAN's squeaky-clean box
Phytosanitary treatment renders Vulture 2 crate fit for export
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
America's super-secret X-37B plane returns to Earth after nearly TWO YEARS aloft
674 days in space for US Air Force's mystery orbital vehicle
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.
Cloud and hybrid-cloud data protection for VMware
Learn how quick and easy it is to configure backups and perform restores for VMware environments.
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.