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.

Cubie paths

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 n².

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 n²/log n(arxiv.org/abs/1106.5736).

Helping humans

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 n²/log n. His first task is to work out how to turn that into an exact number for given sizes of cube.

Less-scrambled cubes

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