For Northeastern University computer scientists Gene Cooperman and Daniel Kunkle, Rubik’s Cube isn’t a game—it’s the ultimate combinatorial puzzle, and their solution promises to improve all our lives. When a Rubik’s speed champion solves the cube, he’s just solving one version of many possible mixed-up states the cube could be in. But what’s the quickest way to solve any possible cube?
The answer isn’t easy, Kunkle points out: The cube has 43 quintillion possible states, and evaluating them all is a big task. One such computation took 8,000 central processing unit hours (equal to running a home computer for an entire year) and generated 120 terabytes of data.
“The basic line of attack is to break it down into subproblems, and then you prove those optimally,” says Kunkle. He and Cooperman used supercomputers and mathematical group theory to solve all possible states of the cube in 26 moves. Granted, that’s not exactly an earth-shattering improvement over the previous record of 27 moves. But Cooperman and Kunkle say their particular method for searching and enumerating states of the cube can be applied to even bigger problems. The methods they used to explore the countless routes to a Rubik’s Cube solution could also be used to identify the best flight schedule or the fastest way to route phone calls.
