Omniscient Being Could Solve Any Rubik's Cube in 20 Moves

By Joseph Calamia | August 12, 2010 3:11 pm

rubiksScientists have cranked through the numbers and determined that no matter how you mangle a Rubik’s Cube, if you’re doing it right you can theoretically solve the puzzle in 20 moves or fewer. By doing it right, we mean doing it like a supercomputer: Researchers tapped Google’s spare computing power to burn through the Cube’s 43,252,003,274,489,856,000 starting positions.

Even given Google’s processing power, the team–which included a mathematician, a Google engineer, a math teacher, and a programmer–could not solve the problem using brute force alone. They had to take all the starting positions and divide them into more manageable chunks, 2.2 billion smaller groups called “corsets,” which Google’s computers could solve simultaneously.

“The primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate,” says Tomas Rokicki, a programmer from Palo Alto, California, who has spent 15 years searching for the minimum number of moves guaranteed to solve any configuration of the Rubik’s cube. [New Scientist]

Though smaller, these 2.2 billion groups also each had about 20 billion starting positions.

The subproblems were small enough to fit in the memory of a modern PC. But it would take an Intel four-core, 2.8-GHz Nehalem chip-based desktop computer 1.1 billion seconds, or about 35 years, to perform the calculation. So the team turned to the impressive computing power that Google has to solve the problem. (Google won’t disclose exactly what kind of computing resources it offered to the group.) [Wired]

Mathematicians have slowly whittled down the believed minimum number of moves to solve the Cube from any starting position, the so called “God’s number,” since the Cube’s creation in 1974 by Hungarian Erno Rubik. Many believed that 20 was the answer for some time, but no one had run through the starting positions to prove it.

[Team member Morley] Davidson said this was “pure religion” as no-one had managed to crunch their way through all configurations. “We were secretly hoping in our tests that there would be one that required 21,” he said. [BBC]

Still, the researchers suggest, don’t expect the confidence boost of a known 20-move maximum to help you solve the Cube any faster.

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. [Team website]

Related content:
80beats: Has the Devilish Math Problem “P vs NP” Finally Been Solved?
80beats: Brilliant & Reclusive Russian Mathematician Doesn’t Need Your Prize Money
80beats: Can a Google Algorithm Predict Nobel Prize Winners?
Discoblog: Book-Balancing, Rubik’s Cube-Solving, Pi-Reciting Geek Girl Goes Viral
Discoblog: A Rubik’s Cube Could Tell Us Which Arm Is an Octopus’ Favorite

Image: flickr / kirtaph

CATEGORIZED UNDER: Physics & Math
  • Nemesis

    It really wasn’t all that hard, either.

  • http://Untitledvanityproject.blogspot.com Rhacodactylus

    LoL, sure glad we didn’t waste this computing power trying to fold proteins, or something silly like that =)

  • mo

    No sh_t. Kinda 8( to be typing on a google phone right now.

  • amphiox

    Hmm. It’s actually kind of strange that a 40 move algorithm would be harder to memorize than a 20 move one.

  • http://rubiksolve.com Cedric

    http://rubiksolve.com

    You can try it yourself with your own cube. It isn’t always 20 moves since it is limited by being web based, but its never over 25. It uses a version of the algorithm outlined in the article above.

  • http://chacaturian.com Ruben

    I’d like to know how they came up with the number of positions figure. It is understandable that the cube cannot be in ANY position. That is to say if you took a naked cube and were to stick on your colorful stickers, the cube may not be solvable. You will find that’s true when you’ve cheated on a cube and swapped stickers – you most likely cannot solve it any more.
    That’s why I’m wondering how they came up with the number of all the positions…

  • Chris the Canadian

    Well gee, I’m glad THAT world dilemma was finally solved. This is news and science HOW???? I love Discovery.com but THIS, to me, is a completely needless and useless story. Tells me that some people, and computers, have too much time on their hands.

  • Bob Snyder

    @amphiox – The more complex algorithms will solve the cube in less moves than the less complex. There would be no reason to have “more complex” algorithms if the “less complex” solved the cube in less moves.

  • Dan

    New knowledge gained is never a waste. You can not totally predict how these results may or may not be used into other applications or sparking further research.

  • http://supermonkeycube.blogspot.com SuperMonkeyCube

    @Ruben – It is much easier to do the math when you think of it in pieces instead of stickers. There are eight corner pieces (three stickers apiece) and twelve edge pieces (two stickers apiece) and the six center pieces that form the framework of the cube. Each edge piece has two possible orientations, each corner has three possible orientations. However, in a solvable cube, there is parity in the orientation – you can’t have only one edge flipped, they have to happen in pairs. The corners are opposite pairs of twists or three in the same direction. Also, you can’t have only two pieces out of position, there is a minimum of three. So if you took all the ways the pieces could be assembled and then divided out the unsolvable states, you get

    8! (corner positions) * 12!(edge positions) * 3^8 (corner orientations) * 2^12 (edge orientations) * (1/12) (dividing out location parity, edge orientation parity, and corner orientation parity).

    43,252,003,274,489,856,000

    @amphiox – It’s not like it’s the same 20 moves for every unsolved case. You would have to know the 20 moves for each of the 43 quintillion cases. Even a 40-move solution involves memorizing solutions for over 1200 last layer cases after part of the cube was already completed. Most solvers memorize between 30 and 80 cases and finish in under 80 moves (although most of the time it’s closer to 65.)

    @Chris the Canadian – If you think that math is only what you can do with a calculator, then you miss the point of this entirely. Looking at a small system with a few degrees of freedom (a Rubik’s Cube) gives us ideas about how information is encoded, it gives us ideas about how complexity arises from a simple system (like DNA?) or maybe insight into compression algorithms for music encoding or data encryption. Even learning how to tackle a problem like this gives us insight into how to deal with brute force solutions.

  • Kevin

    Just for the record, they divided the cube group into ‘cosets’ not ‘corsets’. But yeah, I’ll be looking for a publication on this. Its pretty sweet. Pure research is invaluable to the advancement of our knowledge of all things.

  • http://mashget.wordpress.com/ Cleo Kuehnle

    37. F*ckin’ tremendous things here. I’m very glad to see your article. Thanks a lot and i’m looking forward to contact you. Will you please drop me a mail?

  • philip

    can some one please post a link how to solve it in 30 or less moves…

  • TexasJester

    I graduated high school in 1982 – and was a part of the Cube Craze. There was a booklet out in 1981 that told you how to solve it – there was just so many moves to be done when any piece was in any position. My fastest time to solve it was 27 seconds – a classmate did it in 24 seconds. Once you know the moves, it’s not hard!

    Wish I still had that booklet – I’d post the name and author… Might be google-able…

  • Mitra Mojarrabian

    Need to know the instruction to Solve Rubic Qube.

  • Joey

    if i may, i would have to say that SuperMonkeyCube is quite posibbly the only person here who understood the reason for the research. thet commented on a regular computer chip processing power and then said that Google was able to help solve this problem in what im sure is considerably less then 35 years. the Rubix-Cube was just a problem, its great that we now know it can be solved in 20 moves. but the point of this story is that we can figure something like that out of the 43,252,003,274,489,856,000 problems we started with. and a little side note about this from Google. they recently lent that processing power of theres to a project that can now decode any idvidual genome in two hours for less then a few grand. if im not mistaken it took the decoding of the first human genome about 13 years and cost considerably more then what it cost today. getting somebody to read it for you will cost a bit more but immagin what we can do tomorrow…

  • http://www.jixhost.com JixHost

    Remember all the variants of the cube that followed…

    Im not sure if the 80 s just had so many neat things or was it just that I was in the wonder years…

NEW ON DISCOVER
OPEN
CITIZEN SCIENCE
ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

80beats

80beats is DISCOVER's news aggregator, weaving together the choicest tidbits from the best articles covering the day's most compelling topics.
ADVERTISEMENT

See More

ADVERTISEMENT
Collapse bottom bar
+

Login to your Account

X
E-mail address:
Password:
Remember me
Forgot your password?
No problem. Click here to have it e-mailed to you.

Not Registered Yet?

Register now for FREE. Registration only takes a few minutes to complete. Register now »