If you thought solving a Rubik’s cube was difficult, you were right and maths can back you up. A recent study shows that the question of whether a scrambled Rubik’s cube of any size can be solved in a given number of moves is what’s called NP-complete – that’s maths lingo for a problem even mathematicians find hard to solve.
To prove that the problem is NP-complete, Massachusetts Institute of Technology researchers Erik Demaine, Sarah Eisenstat, and Mikhail Rudoy showed that figuring out how to solve a Rubik’s cube with any number of squares on a side in the smallest number of moves will also give you a solution to another problem known to be NP-complete: the Hamiltonian path problem.
That question asks whether there is route that visits each vertex exactly once in a given graph consisting of a collection of vertices connected by edges, like a triangle, pentagram, or the vast connections in a social network such as Facebook.
It’s reminiscent of the travelling salesperson problem, which aims to find the shortest route that visits several cities only once, probably the most famous NP-complete question of all. “It’s very clever. The description of how it works is very clean,” says Jeff Erickson of the University of Illinois Urbana-Champaign.
NP-complete problems are easy to check, if you’re given a proposed solution, but the amount of time it takes to solve them explodes as the number of inputs goes up, at least with the algorithms we know about today. On the other hand, problems that have algorithms that run their course in a more reasonable amount of time based on the number of inputs are called P.
Researchers are still unsure whether algorithms exist that can solve NP-complete problems faster. This question, often called the P vs NP problem, is one of the most important unsolved maths problems and will net the solver a $1,000,000 prize from the Clay Mathematics Institute of Cambridge, Massachusetts.
So if you’re frustrated about how long it’s taking you to solve a Rubik’s cube, it’s not just you. “You have the excuse now: Rubik’s cubes are legitimately hard,” Rudoy says. You’re not going to figure it out quickly, so you might as well sit back and enjoy the puzzle.
Playing God
Every standard 3x3x3 Rubik’s cube can be solved in a maximum of 20 moves from any starting position, no matter how scrambled. In 2010, programmers found that 20 is the colourful puzzle’s so-called “God’s number”, a name they selected to suggest that even a deity couldn’t solve a Rubik’s cube any faster.
A year later, Demaine, Eisenstat and their colleagues devised a formula to solve a Rubik’s cube with sides of any length and found that the number of moves required for a cube of side n is proportional to n2/log n.
Finding God’s number for a cube with n=3 took several years of computing time and Demaine estimates that the n=4 case would take billions of times longer. “I conjecture it will never be fully solved,” he says.
God’s number is the upper limit for the most scrambled cubes, but many cubes will not take that long. Figuring out whether any given configuration of a cube will take fewer moves is tricky. “We know an algorithm to solve all cubes in a reasonable amount of time,” Demaine says. “But if I give you a particular configuration of the cube, and then you want to solve it with the fewest moves for that configuration, that’s really tough.”
Demaine started working on the question after seeing it in a post from Erickson on a computer science forum, although Erickson says the question had been floating around for a while. “It’s nice to see it finally closed off,” he says.
