# Study uncovers every possible Rubik's Cube solution

##### Aug 13, 2010

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.

## Related Stories

#### Review: Rubik's TouchCube a little too touchy

Sep 23, 2009

(AP) -- Thirty years ago Erno Rubik took a puzzle he had been tinkering with and turned it into the must-have brain twister toy, the Rubik's Cube.

#### Vitamin B1 biosynthesis: Think Rubik's cube

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

#### Aussie ingenuity helps NASA search for new planets

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

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

Jul 08, 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 ...

#### Getting a grip on school timetables

Jan 06, 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.

#### Digital communication technology helps clear path to personalized therapies

Jan 09, 2009

Researchers at the Burnham Institute for Medical Research (Burnham) have shown that search algorithms used in digital communications can help scientists identify effective multi-drug combinations. The study, led by Giovanni ...

## Recommended for you

#### UT Dallas professor to develop framework to protect computers' cores

12 hours ago

UT Dallas cybersecurity expert Dr. Zhiqiang Lin has received funding from the U.S. Air Force to develop a defense framework that burrows deep into a computer system to protect its core.

#### Researcher finds hidden efficiencies in computer architecture

16 hours ago

The computer is one of the most complex machines ever devised and most of us only ever interact with its simplest features. For each keystroke and web-click, thousands of instructions must be communicated ...

#### Scientists apply new graph programming method for evolving exascale applications

18 hours ago

(Phys.org) —Hiding the complexities that underpin exascale system operations from application developers is a critical challenge facing teams designing next-generation supercomputers. One way that computer ...

Apr 17, 2014

(Phys.org) —Google engineers working on software to automatically read home and business addresses off photographs taken by Street View vehicles, have created a product so good that not only can it be used ...

#### Preventing AI from developing anti-social and potentially harmful behaviour

Apr 17, 2014

Next time you play a computer at chess, think about the implications if you beat it. It could be a very sore loser!

#### Researcher seeks to lessen failures in computerized visual recognition programs

Apr 17, 2014

Computer programs that use facial or image recognition systems—be it security cameras or applications that search databases for everything from photographs of wanted criminals to images of bears – are like any other technological ...

##### 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! ;)

## More news stories

#### Going nuts? Turkey looks to pistachios to heat new eco-city

Pistachios are already a key ingredient in Turkish baklava, but the country may now have found a new way to exploit the nuts known as "green gold"—by using their shells to heat a new eco-city.

#### Five features an Amazon phone might offer (Update)

A report this week in The Wall Street Journal that Amazon is planning to release a smartphone has prompted industry analysts and technology blogs to muse about what the device might offer.

#### All-in-One Media Keyboard offers navigation from the couch

(Phys.org) —Microsoft this week announced its All-in-One Media Keyboard. This is a peripheral that is targeted for users who want a comfortable, useful keyboard to use whether sitting on the living room ...

#### LinkedIn membership hits 300 million

The career-focused social network LinkedIn announced Friday it has 300 million members, with more than half the total outside the United States.

#### Researchers uncover likely creator of Bitcoin

The primary author of the celebrated Bitcoin paper, and therefore probable creator of Bitcoin, is most likely Nick Szabo, a blogger and former George Washington University law professor, according to students ...

#### New, more versatile version of Geckskin: Gecko-like adhesives now useful for real world surfaces

(Phys.org) —The ability to stick objects to a wide range of surfaces such as drywall, wood, metal and glass with a single adhesive has been the elusive goal of many research teams across the world, but ...

#### Space-tested fluid flow concept advances infectious disease diagnoses

A new medical-testing device is being prepped to enter the battle against infectious disease. This instrument could improve diagnosis of certain diseases in remote areas, thanks in part to knowledge gained ...

#### Impact glass stores biodata for millions of years

(Phys.org) —Bits of plant life encapsulated in molten glass by asteroid and comet impacts millions of years ago give geologists information about climate and life forms on the ancient Earth. Scientists ...

#### Astronomers discover first self-lensing binary star system

(Phys.org) —A pair of astronomers at the University of Washington has discovered the first known instance of a self-lensing binary-star system. In their paper published in the journal Science, Ethan Kruse ...

#### 'Dressed' laser aimed at clouds may be key to inducing rain, lightning

The adage "Everyone complains about the weather but nobody does anything about it," may one day be obsolete if researchers at the University of Central Florida's College of Optics & Photonics and the University ...