rofessor Gene Cooperman and
graduate student Dan Kunkle have
been showered with international

media attention since announcing in May
that they could solve any configuration of a
Rubik’s Cube in 26 moves—a new record.

News outlets ranging from Discover
magazine to the BBC to the Budapest
(Hungary) Times (the Rubik’s cube was
invented by a Hungarian professor of
architecture) have covered the story, giving
CCIS an extraordinary boost in visibility.

“The Rubik’s Cube is a testing ground for
problems of search and enumeration,”

“faster” way of computing moves, and
even whole groups of moves, by using
mathematical group theory.

Cooperman and Kunkle put all of the
configurations of a Rubik’s Cube in a family
of sets of configurations (called a family
of cosets in mathematical group theory).
They then looked at the result of applying
a single move to all of the configurations
of a coset at once.They simulated this on
a computer at a rate of 10,000,000 times
per second, using a new technique.

In May 1997, UCLA computer science
Professor Richard Korf announced that
he had found the first optimal solutions to
Rubik’s Cube. His research showed that
the median optimal solution was 18 moves,
and researchers believe any cube can be
solved in no more than 20 moves. However,

says Cooperman. “Search and enumeration
is a large research area encompassing
many researchers working in different
disciplines—from artificial intelligence
to operations research. The Rubik’s Cube
allows researchers from different disciplines
to compare their methods on a single,
well-known problem.”

Cooperman and Kunkle set their new
record by using two primary techniques:
They used 7 terabytes of distributed disk
as an extension to RAM, in order to hold
some large tables and developed a new,

Korf was unable to prove this, and no one
has ever been able to prove that it could be
solved in less than 27 moves.

“Our program first does a precomputation
using the seven terabytes of disk space in
order to produce a table of less than one
terabyte,” says Kunkle. “Our program then
uses the table to very quickly—in about a
second—find a solution in 26 moves or less
for any state of Rubik’s Cube.

Cooperman and Kunkle used computers at
Teragrid (teragrid.org) and at Northeastern,
part of the first node from a $200,000 grant
Cooperman and colleagues received from
the National Science Foundation in 2006
to obtain 20 terabytes of storage.

They presented their result July 29 at the
International Symposium on Symbolic and
Algebraic Computation in Waterloo, Ontario.