麻豆传媒

ERIK AKKERSDIJK holds the world record for doing it in 7.08 seconds (). Thibaut Jacquinot does it with one hand (). Seventeen-year-old Joey Gouly likes to do it blindfolded and Zbigniew Zborowski has done it a staggering 3390 times in one day. They are all experts at solving the Rubik鈥檚 cube, the must-have toy of the 1980s and one of the most popular games in history.

Since the first world championship was established in 1982, the record for solving the Rubik鈥檚 cube has been slashed from 19 seconds to just over 7 seconds. But it鈥檚 not just gamers who are interested in solving the Rubik鈥檚 cube. Mathematicians are just as fascinated by this toy. For them, the question is: how many moves are needed to solve a maximally jumbled-up Rubik鈥檚 cube? In other words, what is the smallest number n for which you can be sure that no configuration will require more than n moves to solve?

The answer isn鈥檛 as straightforward as it might seem. If you take a completed cube and jumble it up by rotating its faces at random 25 times, it鈥檚 obvious that you can solve that cube in 25 moves. But that鈥檚 no guarantee that it couldn鈥檛 be solved in fewer than 25 moves, and mathematicians are interested in the optimal solution 鈥� the shortest way to solve any given configuration. Admittedly it鈥檚 a bit of a fringe problem, but mathematicians take this issue deadly seriously; they refer to that number n as 鈥淕od鈥檚 number鈥�.

鈥淢athematicians take this issue deadly seriously; they refer to that number as God鈥檚 number鈥�

You would think that with the dazzling computer power available today, finding this number would just be a matter of crunching through the problem for a few hours or days. Not so, says Tomas Rokicki, a California-based mathematician who founded software firm Instantis. 鈥淭his puzzle, this toy, is so simple, with so few pieces,鈥� he says. 鈥淵et it takes years of processor time to determine some of its most basic properties.鈥�

Little by little, however, mathematicians have placed ever tighter upper bounds on God鈥檚 number. Now Rokicki seems to be close to a definitive answer, and since April he has lowered the upper estimate three times. Could the ultimate prize finally be in sight?

The Rubik鈥檚 cube craze began in 1980, six years after it was invented by Hungarian sculptor and architect Erno Rubik. All told, something like 300 million cubes have been sold worldwide, and a recent survey by voted it the biggest gaming craze in history, edging out the first personal computers like the Sinclair ZX Spectrum in second place and the humble yo-yo in third.

Rubik鈥檚 classic cube is a mechanical puzzle made from small cubes or 鈥渃ubies鈥� arranged in a 3 脳 3 脳 3 array. Each 3 脳 3 鈥渟lice鈥� can be rotated independently, and the cubies鈥� faces each bear a sticker in any one of six colours. Solving the puzzle involves twisting any one of the slices clockwise or anticlockwise until each face has all nine stickers of the same colour.

The problem for mathematicians is that this gives the cube roughly 43 billion billion (43 脳 10¹⁸) different possible configurations. This many Rubik鈥檚 cubes, stacked one on another, would stretch to the sun and back more than eight million times. And there are 18 possible ways to alter any one of these configurations 鈥� a half turn or quarter turn in either direction for each of the six faces. This makes for such complexity that the problem can鈥檛 be solved by what mathematicians call a 鈥渂rute force鈥� approach, solving every possible configuration individually. So God鈥檚 number has remained an enigma, with enthusiasts harnessing ever-greater computing power to devise progressively better estimates for it.

To give computers a chance, mathematicians have had to find tricks to simplify the problem. Fortunately, the Rubik鈥檚 cube is a highly symmetric system. Since the equations don鈥檛 care which side is up, red or blue or whatever, symmetry reduces the magnitude of the problem by nearly a factor of a hundred, leaving a mere 450 million billion configurations to solve. Thinning out the problem like this is encouraging, but solving each remaining configuration directly would still take three million computers more than three million years, according to Rokicki.

So how come 鈥渟peed-cubers鈥�, who compete on the world stage for record times, can unravel a jumbled cube in a matter of seconds? Leyan Lo, a speed-cuber and student at Stanford University in California, says the most common speed-cubing method is thanks to Jessica Fridrich, a famous cuber now at the State University of New York at Binghamton. In 1982 Fridrich devised a technique that relies on a 鈥渨ay-station鈥� configuration 鈥� an intermediate arrangement that is part way toward the solved cube. Her chosen arrangement is a cube with a 鈥渃ross鈥� on one face 鈥� made up of, say, a red centre cubie with four adjacent red cubies. She found she could reach this from any random configuration in about seven moves.

With the cross in place, the cuber works on the corners, then the middle layer, with a separate algorithm 鈥� or combination of moves 鈥� for each possible configuration that might be encountered at each stage. By breaking the problem down in this way, Fridrich created a series of algorithms that can be memorised. While this approach is useful in speed competitions, it rarely yields the solution with the least moves. Lo says that with this approach you can solve a cube in 56 moves on average.

That鈥檚 an enormous number by mathematicians鈥� standards, yet mathematicians have been following a similar strategy in their hunt for God鈥檚 number. The idea is that by defining a suitable way-station configuration and then optimally solving it, it might be possible to work out how many moves it takes to get to the way station from any random configuration. Add that number to the solution from the way-station configuration, and you have an upper bound for God鈥檚 number. Combined with estimates of a lower bound (see 鈥淏ottom up鈥�), this allows mathematicians to home in on the true value.

Rather than using a single configuration as a way station, it is more efficient to deal with hundreds or millions of them in a single calculation. That means turning to a branch of mathematics called group theory, which deals with systems that display symmetry. It is used to simplify calculations of the properties of symmetric molecules, for example, and in May, two of the founders of modern group theory were awarded this year鈥檚 Abel prize, one of the most prestigious accolades in mathematics.

The tools of group theory can simplify the calculations by defining subgroups of hundreds or millions of different configurations with shared mathematical properties. In 1992 Herbert Kociemba, a mathematician from Darmstadt, Germany, came up with a cunning way to break down the cube鈥檚 43 billion billion possibilities. Rather than basing it on specific cube configurations, he devised a particular subgroup based on a set of 10 of the 18 possible moves of the cube, such as a 90-degree turn of the top or bottom face. Using combinations of just these 10 moves, he found that he could reach about 20 billion different configurations from a solved cube.

This was an important result, because Kociemba鈥檚 subgroup was small enough to fit in the memory of a standard desktop computer. With a table of these configurations uploaded, each one listed with the number of moves needed to optimally solve it, the computer would still have enough power to calculate the best way to transform any random cube configuration to one of those in the table.

Kociemba wrote a program to do precisely this. Called Cube Explorer, it takes any arbitrary cube configuration and compares it against the table to determine how many moves are needed to bring it within the subgroup. The longest sequence it finds, added to the number of moves needed to solve it from the configuration in the subgroup, provides an estimate for an upper limit to God鈥檚 number. By 1995 Michael Reid, a mathematician at the University of Central Florida in Orlando, had developed a program based on Cube Explorer and used it to show this upper bound was 30: 12 at most to get to Kociemba鈥檚 subgroup from any jumbled cube, and 18 at most to solve it from the subgroup.

So God鈥檚 number is 30, right? Not quite. To reach a solution using this technique, the cube must pass through a way-station class of configurations, such as Kociemba鈥檚 10-move subgroup. Yet how do you know that the actual fastest solution passes through that particular class of configurations, asks Richard Korf, a mathematician at the University of California, Los Angeles. 鈥淭he shortest path from point A to point B, combined with a shortest path from point B to point C, in general is not the shortest path from point A to point C.鈥� (Indeed, most people in the know believe God鈥檚 number is in fact 20.) Imagine, for example, starting with a cube just one move from solved. If that move isn鈥檛 one of Kociemba鈥檚 10 allowed moves, you might have to make a lot of rotations to get it to one of those 20 billion configurations that can be solved with just those 10. This means that one way to reduce the upper bound is to expand the class size of way-station configurations, thus increasing the probability that an optimal solution will pass through the class.

During the next decade, mathematicians used this trick and others to chip away at the problem. By 2006, the upper bound of God鈥檚 number had fallen to just 27. The next advance occurred in 2007. Dan Kunkle and Gene Cooperman of Northeastern University in Boston devised a way to construct 1.5 trillion groups called cosets, each of about 660,000 configurations that could be reached using only six moves, a half turn of each face. By considering symmetries, they then identified 15,000 in each coset as unique. Next they showed that these could all be solved in 13 or fewer moves. Finally, they came up with a method to transform all other configurations in the coset into one of these 15,000. Solving just one of these 15,000 was thus equivalent to solving the whole coset.

These calculations required access to tremendous computing power, so Kunkle and Cooperman rounded up some 7 terabytes of computer memory to keep track of all configurations. After an incredible 8000 hours of processing time, . Unfortunately, reducing the bound any further would have required hundreds of times more memory than the 7 terabytes available to them. Clearly a new approach was needed.

That鈥檚 where Rokicki came in. Rokicki has been hunting God鈥檚 number for some 15 years now. In recent years, with some help from mathematician Silviu Radu at the Johannes Kepler University in Linz, Austria, he鈥檚 been turning the Cube Explorer idea inside out. The program works by solving each jumbled cube configuration many times over, each time calculating a candidate pathway and retaining only the shortest ones. Rokicki realised that the first parts of the pathways computed by Cube Explorer 鈥� converting a jumbled cube into one in Kociemba鈥檚 subgroup 鈥� are actually solutions to a large set of related configurations, so he decided to exploit this.

He divided up the problem into 2 billion cosets, each containing around 20 billion related configurations. His program then works through one coset at a time, building a list of the moves that turn each of its 20 billion configurations into one of those in Kociemba鈥檚 subgroup, until all of the configurations in the coset have been solved at least once. The longest sequence the program finds is the upper bound for the whole coset. 鈥淚nstead of solving a single configuration in about a second, I solve about 20 billion configurations in about 25 minutes,鈥� says Rokicki. The result? In March Rokicki revealed he had found an upper bound of 25 and on the arXiv preprint server. However, without access to more computational muscle, he couldn鈥檛 get any further.

Enter John Welborn of Sony Pictures Imageworks, the company that put in the computational legwork for the digital special effects in films like Spider-Man 3 and I Am Legend. When Rokicki鈥檚 proof of the 25-move limit was featured on the website Slashdot, it caught Welborn鈥檚 eye. He contacted Rokicki and offered up some of the down time on the firm鈥檚 hundreds of computers. By April, having clocked up more than a year of processing time, Rokicki and Welborn were able to obtain an upper bound of 24. Just two weeks later, with nearly seven more years of processor time under their belt, . Then, in early June, Rokicki revealed to 麻豆传媒 that they had reached 22. It required the analysis of 1,265,326 sets and took an additional 50 years or so of processor time.

This record will stand until Rokicki, or a competitor, finds further shortcuts; proving God鈥檚 number really is 20 is likely to require hundreds of times more computation than 22 did. This time Sony may not be so keen to help.

What about throwing the problem to 鈥淏lue gene/L鈥�, one of the world鈥檚 fastest supercomputers based at the Lawrence Livermore National Laboratory in California? 鈥淚t would take about 900 hours, or about 38 days,鈥� Rokicki estimates. 鈥淏ut that鈥檚 a long time to tie up that asset.鈥�

How about splitting up the problem and distributing it to any web users willing to donate their computers鈥� idle time 鈥� as has already happened with projects like the Einstein@home hunt for neutron stars? Rokicki doesn鈥檛 think it would be possible, since it would require 30,000 people to commit their computers to the project. Besides, as he points out, most home PCs simply don鈥檛 have enough accessible memory.

Instead, Rokicki is working out how to throw ever more computational power and group-theory trickery at the problem, to nail God鈥檚 number once and for all. Most of the available evidence points to the fact that it is 20, says Rokicki 鈥� at least that鈥檚 what solving more than 4 million billion cube configurations has told him so far. But in the cut-and-dried world of maths, that鈥檚 not enough. 鈥淚n no way is it a logical proof; it鈥檚 the difference between actually knowing and surmising,鈥� he says. 鈥淢athematics is full of stuff like that.鈥�