It’s a toy that most kids have played with at one time or another, but the find­ings of North­eastern Uni­ver­sity Com­puter Sci­ence pro­fessor Gene Coop­erman and grad­uate stu­dent Dan Kunkle are not child’s play. The two have proven that 26 moves suf­fice to solve any con­fig­u­ra­tion of a Rubik’s cube – a new record. His­tor­i­cally the best that had been proved was 27 moves.

Why the fas­ci­na­tion with the pop­ular puzzle?

The Rubik’s cube is a testing ground for prob­lems of search and enu­mer­a­tion,” says Coop­erman. “Search and enu­mer­a­tion is a large research area encom­passing many researchers working in dif­ferent dis­ci­plines – from arti­fi­cial intel­li­gence to oper­a­tions. The Rubik’s cube allows researchers from dif­ferent dis­ci­plines to com­pare their methods on a single, well-​​known problem.”

Coop­erman and Kunkle were able to accom­plish this new record through two pri­mary tech­niques: They used 7 ter­abytes of dis­trib­uted disk as an exten­sion to RAM, in order to hold some large tables and devel­oped a new, “faster faster” way of com­puting moves, and even whole groups of moves, by using math­e­mat­ical group theory.

Coop­erman and Kunkle put all of the con­fig­u­ra­tions of a Rubik’s cube in a family of sets of con­fig­u­ra­tions (called a family of cosets in math­e­mat­ical group theory). They then looked at the result of applying a single move to all of the con­fig­u­ra­tions of a coset at once. They sim­u­lated this on a com­puter at a rate of 100,000,000 times per second, using a new tech­nique in math­e­mat­ical group theory.

In May 1997, U.C.L.A. com­puter sci­ence Pro­fessor Richard Korf announced that he had found the first optimal solu­tions to Rubik’s Cube. His research showed that the median optimal solu­tion was 18 moves, and he believed any cube could be solved in no more than 20 moves. How­ever, he was unable to prove this, and no one has ever been able to prove that it could be solved in less than 27 moves.

Korf had written a pro­gram that spends a long time to find optimal solu­tions for single states of the Rubik’s cube,” says Kunkle. “Our pro­gram first does a large pre-​​computation and then it very quickly — in about a second — finds a solu­tion in 26 moves or less for any state of Rubik’s cube.

Coop­erman and Kunkle used com­puters at Ter­a­grid (ter​a​grid​.org) and at North­eastern, part of the first node from a $200,000 grant Coop­erman and col­leagues received from the National Sci­ence Foun­da­tion in 2006 to obtain 20 ter­abytes of storage.

Rubik’s Cube, invented in the late 1970s by Erno Rubik of Hun­gary, is per­haps the most famous com­bi­na­to­rial puzzle of its time. Its pack­aging boasts bil­lions of com­bi­na­tions, which is actu­ally an under­state­ment. In fact, there are more than 43 quin­til­lion (4.3252 x 10**19) dif­ferent states that can be reached from any given configuration.

About North­eastern: Founded in 1898, North­eastern Uni­ver­sity is a pri­vate research uni­ver­sity located in the heart of Boston. North­eastern is a leader in inter­dis­ci­pli­nary research, urban engage­ment, and the inte­gra­tion of class­room learning with real-​​world expe­ri­ence. The university’s dis­tinc­tive coop­er­a­tive edu­ca­tion pro­gram, where stu­dents alter­nate semes­ters of full-​​time study with semes­ters of paid work in fields rel­e­vant to their pro­fes­sional inter­ests and major, is one of the largest and most inno­v­a­tive in the world. The Uni­ver­sity offers a com­pre­hen­sive range of under­grad­uate and grad­uate pro­grams leading to degrees through the doc­torate in six under­grad­uate col­leges, eight grad­uate schools, and two part-​​time divi­sions. For more infor­ma­tion, please visit www​.north​eastern​.edu.