Skip to Content
MIT News magazine

Rubik's Cube Math

Solving a cube won’t take more than N2/log N moves
October 25, 2011

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

Keep Reading

Most Popular

conceptual illustration of a heart with an arrow going in on one side and a cursor coming out on the other
conceptual illustration of a heart with an arrow going in on one side and a cursor coming out on the other

Forget dating apps: Here’s how the net’s newest matchmakers help you find love

Fed up with apps, people looking for romance are finding inspiration on Twitter, TikTok—and even email newsletters.

computation concept
computation concept

How AI is reinventing what computers are

Three key ways artificial intelligence is changing what it means to compute.

still from Embodied Intelligence video
still from Embodied Intelligence video

These weird virtual creatures evolve their bodies to solve problems

They show how intelligence and body plans are closely linked—and could unlock AI for robots.

We reviewed three at-home covid tests. The results were mixed.

Over-the-counter coronavirus tests are finally available in the US. Some are more accurate and easier to use than others.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.