Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Intelligent Machines

Rubik's Cube Math

Solving a cube won’t take more than N2/log N moves

In 2010, an international team of researchers proved that no matter how scrambled a Rubik’s cube got, it would require no more than 20 moves to solve it. Their proof, however, relied on the equivalent of 35 years’ worth of number crunching on a good modern computer.

For cubes bigger than the standard Rubik’s cube, adequately canvassing starting positions may well be beyond the computational capacity of all the computers in the world. But in September, Erik Demaine (right), an associate professor of computer science and engineering, led a team including his father, CSAIL visiting professor Martin Demaine (left), that demonstrated the mathematical relationship between the number of squares in a cube and the number of moves in the shortest solution to its most scrambled state.

The standard way to solve a Rubik’s cube is to find a square that’s out of position and move it into place while leaving the rest of the cube as little changed as possible. That yields a worst-case solution whose number of moves is proportional to N2, where N is the number of squares per row. But the team saw that under some circumstances, a single sequence of twists could move multiple squares into place.

This story is part of the November/December 2011 Issue of the MIT News Magazine
See the rest of the issue
Subscribe

Describing those circumstances mathematically was no easy task. “In the first hour, we saw that it had to be at least N2/log N,” Erik Demaine says. “But then it was many months before we could prove that N2/log N was enough moves.”

The latest Insider Conversation is live! Listen to the story behind the story.

Subscribe today
Already a Premium subscriber? Log in.
Next in MIT News
Want more award-winning journalism? Subscribe and become an Insider.
  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

    Bimonthly digital/PDF edition

    Access to the magazine PDF archive—thousands of articles going back to 1899 at your fingertips

    Special interest publications

    Discount to MIT Technology Review events

    Special discounts to select partner offerings

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning print magazine, unlimited online access plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

  • Insider Online Only {! insider.prices.online !}*

    {! insider.display.menuOptionsLabel !}

    Unlimited online access including articles and video, plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

/3
You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.