By Jacob Aron
Only the most hardcore puzzle-solvers ever go beyond the standard 3x3x3 Rubik’s cube, attempting much larger ones such as those pictured on the right. Now an algorithm has been developed that can solve a Rubik’s cube of any size. It might offer clues to humans trying to deal with these tricky beasts.
Rubik’s cube science got a boost last year when a team led by programmer Tomas Rokicki of Palo Alto, California, showed that even the most scrambled standard Rubik’s cube can be solved in 20 moves or less. That feat was a big deal: the figure has been dubbed “God’s number”, the assumption being that the Almighty couldn’t solve it faster. But that result didn’t shed light on the monster cubes.
So Erik Demaine, a computer scientist at the Massachusetts Institute of Technology, set out to find a general algorithm for solving a cube with any side-length – of n squares.
The new approach differs from that of Rokicki’s. The latter used a “brute force” method, relying on computers borrowed from Google to check all 43 quintillion possible solutions, but Demaine says doing the same for larger cubes would be impossible. “You can’t solve all values of n with computational search,” he explains.
Instead, Demaine’s team started by looking at a method Rubik’s cube enthusiasts commonly use to quickly solve the puzzle. Essentially, you try to move a single square, or “cubie”, into the desired position while leaving the rest of the cube as unchanged as possible. Because it’s not possible to move a single cubie without disturbing others, this method is time-consuming, requiring a number of moves that is proportional to n2.
Demaine and his colleagues found a short-cut. Each cubie has a particular path that will place it in the correct position. His algorithm looks for cubies that all need to go in the same direction, then moves them at the same time. “We found that instead of solving one cubie at a time, you can parallelise that process and solve several,” Demaine says.
Grouping cubies with similar paths reduces the number of moves required by a factor of around log n. This means that the maximum number of moves that will ever be required for a cube of side n is proportional to n2/log n(arxiv.org/abs/1106.5736).
Figuring out a single cubie’s path without a computer is no easy task, let alone doing it for the whole cube, so it’s unlikely that humans will be able to directly apply this formula. But Demaine reckons it could offer cube-solvers a few tips.
“It gives me a couple of ideas how to solve this thing faster,” agrees Stewart Clark, a Rubik’s cube enthusiast and physicist at Durham University, UK who owns an 11x11x11 cube.
Clark says it’s possible that some of the techniques behind the algorithm could be applied to speeding up other problems that involve searching or sorting through sets of data with a similar mathematical structure to the cube. “It would need a little bit of tweaking, but there are areas where you might be able to tweak it in the right direction.”
So has the Rubik’s cube given up all of its secrets? No, says Demaine. Right now his algorithm only gives an approximate value for the number of moves required to solve a cube of any given size: it states that the value is proportional to n2/log n. His first task is to work out how to turn that into an exact number for given sizes of cube.
Even then, however, a further puzzle remains. Demaine’s current algorithm only finds the most efficient way to solve a cube if it is in the most scrambled state of that cube possible. But he would also like to explore whether an algorithm exists for finding the number of moves required by less-scrambled cubes.
“Suppose someone takes a solved 20x20x20 Rubik’s cube and makes five moves – can you figure out [from that scrambled state] what those five moves were?” he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. “We don’t know.”
For Rokicki, the next task is to find an algorithm that can solve any 4x4x4 cube in the fewest possible moves. “It would probably take more CPU time to solve a single random 4x4x4 position than we used to prove God’s number for the 3x3x3.”
More on these topics:
By Jacob Aron
It has taken 15 years to get to this point, but it is now clear that every possible scrambled arrangement of the Rubik’s cube can be solved in a maximum of 20 moves – and you don’t even have to take the stickers off.
That’s according to a team who combined the computing might of Google with some clever mathematical insights to check all 43 quintillion possible jumbled positions the cube can take. Their feat solves the biggest remaining puzzle presented by the Rubik’s cube.
“The primary breakthrough was figuring out a way to solve so many positions, all at once, at such a fast rate,” says Tomas Rokicki, a programmer from Palo Alto, California, who has spent 15 years searching for the minimum number of moves guaranteed to solve any configuration of the Rubik’s cube.
The figure is dubbed “God’s number”, the assumption being that even the Almighty couldn’t solve the puzzle faster. New Scientistreported in 2008 that Rokicki had reduced the value of God’s Number to 22, but it was clear that bringing it down further would require some clever shortcuts.
To further simplify the problem, Rokicki and his team have now used techniques from the branch of mathematics called group theory .
First they divided the set of all possible starting configurations into 2.2 billion sets, each containing 19.5 billion configurations, according to how these configurations respond to a group of 10 possible moves.
This grouping allowed the team to reduce the number of sets to just 56 million, by exploiting various symmetries of a cube. For example, turning a scrambled cube upside down doesn’t make it harder to solve, so these equivalent positions can be ignored.
That still left a vast number of starting configurations to check, however, so the team also developed an algorithm that speeds up this process.
Useful dead ends
Previous methods solved around 4000 cubes per second by attempting a set of starting moves, then determining if the resulting position is closer to the solution. If not, the algorithm throws those moves away and starts again.
Rokicki’s key insight was to realise that these dead-end moves are actually solutions to a different starting position, which led him to an algorithm that could try out one billion cubes per second.
You can think of his solution like this. Imagine visiting a friend in an unfamiliar city. They’ve given you directions indicating when to turn left or right, but neglected to include a starting point. If you follow the directions from a random point it’s unlikely you’ll reach your destination, but matching them to the right starting point will definitely get you there.
Similarly, the team’s algorithm rapidly matches moves to the correct starting point, allowing them to solve each set of 19.5 billion in under 20 seconds.
Even at this speed, completing the entire task would take around 35 years on an ordinary computer. So the team’s solution relies on another shortcut: John Dethridge, an engineer at Google in Mountain View, California, was able to use his employers’ vast computing empire to solve the problem in a matter of weeks.
We’ve known for 15 years that some configurations of the cube require just 20 moves to solve – and many mathematicians suspected that none needed more. The team’s exhaustive search proves them right
“Research like this shows how pure mathematics can often be used to make hard computational problems more feasible,” says Mark Kambites, a mathematician at the University of Manchester who was not involved in the team’s work. “The Rubik’s cube is an interesting test case for the methods of computational group theory.”
The work has not yet been peer reviewed but Rokicki points out that it is an extension of earlier work that was published in The Mathematical Intelligencer, which reduced God’s number to 22.
More on these topics: