The search for 'God's Number' in a Rubik's Cube

Remember Rubik's Cube, that devious little puzzle from the 1980s? Well, to paraphrase a movie from that era: It's back!

Cubing -- as it is known -- has had a revival, thanks to the growing popularity of "speedcubing" competitions to see who can take a randomly scrambled cube and solve it the fastest. The world record of 9.86 seconds was set last month at a World Cube Association competition in Spain.

Speedcubing is not so much a test of intuition -- as it was for the hundreds of millions who ultimately threw the cube down in frustration -- but a challenge of dexterity. Speedcubers memorize complex algorithms designed to solve the cube quickly, and then execute those algorithms using special spring-loaded, lubricated cubes. Cubers also compete with one hand, blindfolded, and with their feet.

But perhaps the most difficult challenge in cubing, and the one that has attracted the interest of Northeastern University researchers, is the attempt to determine the minimum number of moves it would take to solve the cube from even the most difficult of its more than 43 quintillion possible arrangements -- that's 43 followed by 18 zeros.

In cubing, this is known as the pursuit of "God's number" (because God would always use the fewest moves possible to solve the puzzle).

Next month, at a symposium in Canada, Dan Kunkle, a doctorate student in computer science, and Gene Cooperman, a professor of computer science, will announce the lowest proven "God's number" to date: 26.

To achieve this feat, they relied not on a religious higher power, but on a computing higher power: 128 CPUs that ran for over 63 hours to do the bulk of the calculation. If you tried the same calculation on a personal computer, it would take about 8,000 hours, according to Kunkle.

Why have Kunkle and Cooperman spent a year-and-a-half holed up in Northeastern's High Performance Computing Lab, not to mention part of a $200,000 grant from the National Science Foundation, trying to find the minimum number of moves to solve a toy?

"It has wide applications in mathematical group theory, enumeration, and search," said Kunkle, a 27-year-old from Rochester, N.Y. "The cube provides us with a discreet thing that we can make discreet choices about," he said, adding that it has practical applications in fields such as scheduling for factories and air traffic control.

Erich Kaltofen, a professor of mathematics and computer science at North Carolina State University who was not involved in the research, said its importance is not about the number 26.

"It seems like a toy problem," he said, "but the emphasis is not to solve the problem but to show that the technology is there to do it. It's more of a test of computing power and mathematical ingenuity. The problem is not finding the minimum number of moves to solve a Rubik's Cube, but to demonstrate that you can carry out such a gigantic combinatorial search."

Kunkle and Cooperman, who is on sabbatical, will present their findings at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario. They will also give a separate lecture on how they "did a really big computation," as Kunkle explains it.

They may need an even bigger computation if they are ever going to nail down the final figure for "God's number." Some theorize that it could be as low as 20 moves.

Created in 1974 by Erno Rubik, a Hungarian sculptor and architecture professor, Rubik's Cube shot to fame in 1980, sold 100 million units by 1982, and has gone on to become the best-selling toy of all-time.

Yet the mathematical possibilities of that little 3x3x3 cube with 54 colored squares -- which Rubik created when he attached elastic bands to wooden blocks and started twisting -- are difficult for the average person to comprehend. "If the 6 billion people on this earth each had their own planet with 6 billion people on it," Kunkle said, "and they each had a Rubik's Cube [in a different arrangement], only one of them would have a solved one."

Kunkle is an amateur speedcuber himself. "I can usually do it in under two minutes," he said, "enough to impress people at parties." But people are dismayed when they learn that there is a mathematical method to the madness.

"They get very disappointed," he said. "They want you to be a genius who can just look at it and solve it."