Study uncovers every possible Rubik's Cube solution

August 13, 2010
Rubik's Cube
Source: wikipedia

An international team of researchers using computer time lent to them by Google has found every way the popular Rubik's Cube puzzle can be solved, and showed it can always be solved in 20 moves or less.

The study is just the latest attempt by Rubik's enthusiasts to figure out the secrets of the cube, which has proven to be altogether far more complicated that its jaunty colors might suggest.

At the crux of the quest has been a bid to determine the lowest number of moves required to get the cube from any given muddled configuration to the color-aligned solution.

"Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube," said the team of mathematicians, who include Morley Davidson of Ohio's Kent State University, Google engineer John Dethridge, German math teacher Herbert Kociemba and Tomas Rokicki, a California programmer.

"There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves."

"One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God's Algorithm. The number of moves this algorithm would take in the worst case is called God's Number. At long last, God's Number has been shown to be 20."

The research, published online, ends a 30-year search for the most efficient way to correctly align the 26 colored cubes that make up Erno Rubrik's 1974 invention.

"It took fifteen years after the introduction of the Cube to find the first position that provably requires 20 moves to solve," the team said. "It is appropriate that fifteen years after that, we prove that twenty moves suffice for all position."

Using computers lent to them by Google -- the company won't disclose how many or how powerful they are -- the team crunched through billions of Cube positions, solving each one over a period of "just a few weeks."

The study builds on the work of a veritable pantheon of Rubik's researchers, starting with Morwen Thistlethwaite who in 1981 showed 52 moves were sufficient to reach the solution from any given Cube position.

By May 1992, Michael Reid showed 39 moves was always sufficient, only to be undercut a mere day later by Dik Winter, who showed 37 moves would work.

Rubik's enthusiasm extends not only to God's number, but the speed with which the tricky puzzle can be solved.

The current world record holder is Dutch Erik Akkersdijk who successfully solved the puzzle in just 7.08 seconds.

Explore further: Aussie ingenuity helps NASA search for new planets

Related Stories

Aussie ingenuity helps NASA search for new planets

March 23, 2005

CSIRO's success with a new manufacturing technique for a piece of astrometry equipment is likely to help American scientists detect planets in our galaxy and beyond. CSIRO Industrial Physics has mastered the manufacturing ...

Vitamin B1 biosynthesis: Think Rubik's cube

November 20, 2008

(PhysOrg.com) -- A key enzyme in the biosynthesis of vitamin B1 has somehow evolved the ability to perform a complex series of some 15 to 20 steps, report two Cornell chemists.

Getting a grip on school timetables

January 6, 2010

A new approach to solving the problem of school timetabling, known as a GRASP, has been developing by researchers in Brazil. They report details in a forthcoming issue of the International Journal of Operational Research.

Mouseless, the 'invisible' computer mouse (w/ Video)

July 8, 2010

(PhysOrg.com) -- Mouseless is a computer mouse that allows you to interact with a computer with a mouse in the same way as usual - except that there is no mouse hardware. The researchers call it an "invisible mouse."

Recommended for you

Software turns smartphones into tools for medical research

July 27, 2015

Jody Kearns doesn't like to spend time obsessing about her Parkinson's disease. The 56-year-old dietitian from Syracuse, New York, had to give up bicycling because the disorder affected her balance. But she still works, drives ...

Where is solar power headed?

July 22, 2015

Most experts agree that to have a shot at curbing the worst impacts of climate change, we need to extricate our society from fossil fuels and ramp up our use of renewable energy.

3 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

trekgeek1
not rated yet Aug 13, 2010
"Gods number"?

Does "God" really need Bosons and algorithms named after him if he/she exists? Let's stop this for Gods sake. (Pun intended).
TheWalrus
not rated yet Aug 13, 2010
Billions of configurations? That's like saying
McDonalds has sold over 2 hamburgers. There are something like 42 quintillion possible Rubik's Cube configurations.
DaveGee
not rated yet Aug 16, 2010
As someone who was a kid when rubics cube came out I'm not too impressed... 20 moves? Bah! How about just a qtr turn followed by just the right amount of upward pressure a few moments later BANG a 'solved' cube! ;)

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.