Scientists are coming closer to solving the mysteries of the Rubik’s Cube, a toy first sold in Hungary 30 years ago. But the daunting numbers spawned by the seemingly simple, multicolored, three-by-three-by-three cube may keep mathematicians and computer scientists occupied for several decades.
Chris Krueger, a 19-year-old student from Denver, won the inaugural Rubik’s Cube Canadian Open in May. (AP photo)
The cube, invented by a Budapest university lecturer in 1974, requires solvers to unscramble the individual 27 cubes so that each of the six three-by-three faces of the larger cube have uniform color. Because each move involves changing the position of nine smaller cubes, solving the cube manually can be a maddening yet entertaining pastime.
Computer scientists are using a more systematic, automated approach to quantify how many moves it takes to solve the Rubik’s cube. That’s understandable, considering that there are nearly 43 quintillion possible configurations (that’s 43 followed by 18 zeroes; for more on the names of big numbers, see this Numbers Guy column). Earlier this year, Northeastern University computer-science graduate student Dan Kunkel and his advisor showed that each one of these configurations could be solved in no more than 26 moves (counting both a quarter-turn of the cube and a half-turn as a single move each). That’s after 27 moves was set as the upper bound last year. This Science News article explains how they did it.
But the minimum number of moves needed remains unknown. University of California, Los Angeles computer science professor Richard Korf, who has studied the cube, told me that computer scientists can find the optimal solution for any one cube, and that some require 20 moves. None have been found to need more, but an infinitesimal fraction of all possibilities have been checked. It takes somewhere around an hour to find the best solution for any one configuration, Prof. Korf said; doing so for all 43 quintillion would take quadrillions of years.
Mr. Kunkel didn’t test every combination individually; he used clever techniques to group the configurations and focus his computer power on the most intractable ones. Prof. Korf mentioned another technique to avoid checking every single one: Start with the solved cube, and make every possible change. All the resulting cubes can be solved in one move. Do the same to those, and disregard any that have already been solved in fewer moves; the rest can be solved in two moves. And continue in that fashion, until all have been solved. Mr. Kunkle said he adapted that method for his purposes. “That would give you the perfect upper bound,” he told me. “The problem is that there are so many states that it’s not feasible with computing resources available at this time.”
Prof. Korf recently applied that technique for a more-manageable problem: confirming that the so-called 15 Puzzle, which involves sliding 15 tiles one at a time around a 4-by-four board to reach a certain layout, requires no more than 80 moves to solve. Confirming that, for a puzzle with one-millionth the number of configurations as the Rubik’s Cube, took a month of computing time.
“Hopefully in our lifetimes this question will be answered,” Prof. Korf said of the Rubik’s Cube, “but not in the next few years, just because the scale of the problem is so large.” Mr. Kunkle added, “It’s sort of a race now. People are trying to shave moves off, doing whatever we can.”