The Rubik's Cube Solution that Could Improve Your Life

Scientists solve it in 26 moves. Next up: flight schedules.

By Anne Casselman|Wednesday, August 15, 2007
RELATED TAGS: MATH

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.

Comment on this article
ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

ADVERTISEMENT
ADVERTISEMENT
Collapse bottom bar
DSCNovCover
+

Log in to your account

X
Email address:
Password:
Remember me
Forgot your password?
No problem. Click here to have it emailed to you.

Not registered yet?

Register now for FREE. It takes only a few seconds to complete. Register now »