Ever since its invention in 1974, the Rubik’s Cube has presented adults, children and hobbyists alike with one challenge: how to make each side a solid color.
Scientists around the world have taken this fascination with Erno Rubik’s invention one step further, trying to discover the quickest way to align the sides.
Last Wednesday, Northeastern computer science professor Gene Cooperman and graduate student Dan Kunkle announced they had discovered a new technique to reduce the maximum number of moves needed to solve the puzzle to 26, thereby beating a previous record of 27 moves.
The previous record, set by University of California Los Angeles computer science professor Richard Korf in 2006, proved that the Cube could be solved in 27 moves. In his research, Korf said any Rubik’s Cube configuration could be properly aligned after about 18 moves or no more than 20 moves, but he could never prove this discovery.
Cooperman has worked with the Rubik’s Cube for more than a decade, while Kunkle said he began his research a year and a half ago and will use it as his thesis project.
“I thought it would be a challenging problem for us,” he said. “When I decided what kind of research I wanted to do in graduate school I thought it would be fun to do something with the Rubik’s cube.”
Kunkle added that he has played with the cube since childhood.
“It was kind of a craze when I was a kid,” he said. “About five years ago when I started college I finally learned how to solve it and was then just wondering how many moves it would take.”
The Cube provides possibilities for researchers in a wide variety of disciplines, Cooperman said.
“The Rubik’s Cube allows researchers from different disciplines to compare their methods on a single, well-known problem,” Cooperman stated in a press release.
The Rubik’s Cube can be arranged in more than 43 quintillion (4.3252 x 10**19) different ways.
Cooperman and Kunkle used a computer with seven terabytes of disks to compute the necessary algorithm. This equipment was provided through a $200,000 grant from Teragrid, a consortium of super-computing sites around the world, to compute a way to solve any combination of Rubik’s Cube configurations.
“We break the problem down into two phases. In the first phase, we consider all the positions you could get to by making only 180 degree turns of all the faces,” Kunkle said. “This gives you a much smaller number of configurations, only half a million.”
Kunkle said the puzzle should then be solved using half-turns, which would require a maximum of 29 moves. He said this number could always be decreased to 26 if the right moves are applied.
Still, websites like “Two-Phase-Algorithm and God’s Algorithm,” at www.kociemba.org/performance, claim it is possible to solve any combination in 20 moves or less.
Kunkle said he is going to continue researching ways to decrease the number of moves needed to solve a Rubik’s Cube.
“I hope to get it down to 20. I think in a decade we’ll get there, if not sooner,” he said.
Cooperman and Kunkle will present an 8-page publication of their work this summer at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Canada. Their research can also be read at Cooperman’s website, www.ccs.neu.edu/home/gene.
