Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

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.

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

0 comments about this story. Start the discussion »

Credit: Dominick Reuter

Tagged: Computing

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me
×

A Place of Inspiration

Understand the technologies that are changing business and driving the new global economy.

September 23-25, 2014
Register »