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.”
10 Breakthrough Technologies 2024
Every year, we look for promising technologies poised to have a real impact on the world. Here are the advances that we think matter most right now.
Scientists are finding signals of long covid in blood. They could lead to new treatments.
Faults in a certain part of the immune system might be at the root of some long covid cases, new research suggests.
AI for everything: 10 Breakthrough Technologies 2024
Generative AI tools like ChatGPT reached mass adoption in record time, and reset the course of an entire industry.
OpenAI teases an amazing new generative video model called Sora
The firm is sharing Sora with a small group of safety testers but the rest of us will have to wait to learn more.
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.