Professor Richard Korf of the Computer Science Department

In research to be presented at the annual American Association of Artificial Intelligence conference in Providence, R.I., on July 28, computer science Professor Richard Korf has found the first optimal solutions to Rubik's Cube. The median optimal solution appears to be 18 moves, and it is believed any cube can be solved in no more than 20 moves.

Rubik's Cube, invented in the late 1970s by Erno Rubik of Hungary, is perhaps the most famous combinatorial puzzle of its time. The standard version consists of a cube with different color stickers on each of the nine subcubes, or cubies, on each exposed face. The popular puzzle is scrambled by making a number of random twists of each cubie, and the task is to restore the cube to its original state.

The problem is difficult, and a slogan on the package boasts billions of combinations, which is actually a considerable understatement. In fact, there are more than 43 quintillion (4.3252 x 10**19) different states that can be reached from any given configuration.

"To solve Rubik's cube, one needs a general strategy, which usually consists of a set of move sequences, or macro operators, that correctly position individual cubies without violating previously positioned ones," Korf said. "Such strategies typically require 50 to 100 moves to solve a randomly scrambled cube. This research shows that most scrambled cubes can be solved in no more than 18 moves," he said.

One of the benefits to Korf's method is its capability for finding the optimal or shortest solution every time. In the research, he generated 10 random problem instances, and all were solved optimally -- one was solved in 16 moves, three in 17 moves, and the remaining six in 18 moves. As far as can be determined, optimal solutions to random instances have not been previously found.

Korf's research, which included participation by graduate students and funding by the National Science Foundation, is detailed in his paper "Finding Optimal Solutions to Rubik's Cube Using Pattern Databases." In unique combination, Korf used pattern databases, heuristic tools, and a search algorithm called iterative-deepening-A*. IDA* is a depth-first search that looks for increasingly longer solutions in a series of iterations, using a lower-bound heuristic to prune branches once their estimated length exceeds the current iterative bound. The heuristic modified the standard use of manhattan distance for sliding tile puzzles. Running the algorithm on a Sun Ultra-Sparc Model 1 workstation, searches to depth 17 (approximately 120 billion possibilities, or nodes) solved problems in two days. Searching to a level 18 depth (more than one trillion nodes) would take about one month.

"In order to solve the puzzle faster, a better heuristic tool should be developed," Korf said. "Also, the speed of the program advances linearly with the amount of memory available. As computer memories become larger and cheaper, we believe that this approach will become increasingly cost effective," he said.

Korf has been a faculty member in the Computer Science department in the School of Engineering and Applied Science since 1985. He received his Ph.D. from Carnegie-Mellon University in 1983. His primary research area is heuristic search algorithms in artificial intelligence. Example problems studied include how to make moves in a game such as chess, how to find a shortest tour of a set of cities (the traveling salesman problem), and constraint-satisfaction problems such as scheduling classrooms, students and instructors at a university. What these combinatorial problems all have in common is an enormous number of possibilities, and the challenge is to develop efficient algorithms to find good solutions within practical computational and memory limitations.