Sudoku Science
16 IEEE Spectrum | February 2006 | NA www.spectrum.ieee.org Millions of people around the world are tackling one of the hardest problems in computer science—without even knowing it. The logic game Sudoku is a miniature version of a longstanding mathematical challenge, and it entices both puzzlers, who see it as an enjoyable plaything, and researchers, who see it as a laboratory for algorithm design. Sudoku has become a worldwide puzzle craze within the past year. Previously known primarily in Japan, it now graces newspapers, Web sites, and best-selling books in dozens of countries [see photo, “Number Fad”]. A puzzle consists of a 9-by-9 grid made up of nine 3-by-3 subgrids. Digits appear in some squares, and based on these starting clues, a player completes the grid so that each row, column, and subgrid contains the digits 1 through 9 exactly once. An easy puzzle requires only simple logical techniques—if a subgrid needs an 8, say, and two of the columns running through it already hold an 8, then the subgrid’s 8 must go in the remaining column. A hard puzzle requires more complex pattern recognition skills; for instance, if a player computes all possible digits for each cell in a subgrid and notices that two cells have exactly the same two choices, those two digits can be eliminated from all other cells in the subgrid. No matter the difficulty level, however, a dedicated puzzler can eventually crack a 9-by-9 Sudoku game. A computer solves a 9-by-9 Sudoku within a second by using logical tricks that are similar to the ones humans use, but finishes much faster [see puzzle, “Challenge”]. On a large scale, however, such shortcuts are not powerful enough, and checking the explosive number of combinations becomes impossible, even for the world’s fastest computers. And no one knows of an algorithm that’s guaranteed to find a solution without trying out a huge number of combinations. This places Sudoku in an infamously difficult class, called NP-complete, that includes problems of great practical importance, such as scheduling, network routing, and gene sequencing. “The question of whether there exists an efficient algorithm for solving these problems is now on just about anyone’s list of the Top 10 unsolved problems in science and mathematics in the world,” says Richard Korf, a computer scientist at the University of California at Los Angeles. The challenge is known as P = NP, where, roughly speaking, P stands for tasks that can be solved efficiently, and NP stands for tasks whose solution can be verified efficiently. (For example, it is easy to verify whether a complete Sudoku is correctly filled in, even though the puzzle may take quite a lot of time to solve.) As a member of the NP-complete subset, NUMBER FAD: A reader examines a Sudoko puzzle in The Independent, London, last May.