Mathematicians find new clues to the popular puzzle

When you get stuck on a fiendishly difficult sudoku, it's hard not to wonder if the puzzle really has a solution. At another moment, aglow in the triumph of a clever deduction, you might have a sneaking suspicion that there may be a simpler, more systematic way of finding the answer. Further questions may come to mind: How many different sudoku puzzles are possible in the standard 9-by-9 format? Can a puzzle with few initial entries be easier to solve than one with more entries? What's the smallest number of initial entries necessary to guarantee that there's one, and only one, solution?

Although the puzzles are often billed as requiring no math to solve, some of the questions they raise call for mathematical analysis. Researchers are now taking up the task. An article in the June Notices of the American Mathematical Society lays a mathematical framework for addressing some basic questions about sudokus.

Each 9-by-9 sudoku grid is composed of nine 3-by-3 subgrids. Initially, some of these 81 squares contain a number, from 1 through 9, but others do not. The object is to fill in the empty squares so that each row, column, and subgrid contains all of the numbers 1 through 9, in any order. Each puzzle has only one solution.

Although sudoku puzzles almost always use the digits 1 through 9, any nine symbols will suffice. For example, a puzzle could have nine letters, shapes, or colors instead of numbers. When graph theorists label the vertices, they call it a "coloring." A sudoku puzzle begins with a partial coloring, since only a few spots have numbers. Once each vertex is colored and no two connected vertices have the same color, the coloring is called "proper."

Thus, in the language of graph theory, solving a sudoku means extending a partial coloring of the graph into a proper coloring.