IT STARTS WITH EULER. Several of the participants in the Great America trip used some of their downtime to work on Su Doku puzzles. There are several different styles of working the puzzles. Some people prefer to work out the solution one absolutely positive entry at a time and they take pride in being able to work the problem in pen. Others are willing to make marginal notes or use trial and error methods. There are ample opportunities for a bit of woofin' at others' solution styles. All of that got me thinking about more efficient algorithms for solving the puzzle. A standard Su Doku puzzle (and this is true even if there are nine colors or nine distinct shapes or any other nine-way characterization) is a 9x9 matrix partitioned into nine 3x3 submatrices with the following properties.

1. Each counting number {1, 2, ..., 9} occurs exactly once in each row.
2. Each counting number {1, 2, ..., 9} occurs exactly once in each column.
3. Each counting number {1, 2, ..., 9} occurs exactly once in each submatrix.

The problem for the puzzle-solver is to use the relatively few numbers given in the puzzle to identify the remaining numbers, using properties 1, 2, and 3 to rule out numbers that do not fit, and with the knowledge that, as with a properly-posed chess problem, there is exactly one solution (no 'twin' solutions where, for example, a 2 or a 9 can solve the puzzle in each of two places within a submatrix.)

Not all puzzles lend themselves to easy elimination of choices. But is there sufficient structure in the problem to come up with an algorithm to solve for all the remaining elements quickly? It has to be the case that, for the top row,

55-a₁₁-a₁₂-a₁₃-b₁₄-b₁₅-b₁₆-c₁₇-c₁₈-c₁₉ = 0,

where the letters identify a particular submatrix (a, b, ..., g, h, j) and the numbers identify the row and column respectively of the matrix. Likewise, in the leftmost column,

55-a₁₁-a₂₁-a₃₁-d₄₁-d₅₁-d₆₁-g₇₁-g₈₁-g₉₁ = 0,

and within the top left submatrix,

55-a₁₁-a₁₂-a₁₃-a₂₁-a₂₂-a₂₃-a₃₁-a₃₂-a₃₃=0.

Thus, if there are fewer than 27 unidentified numbers, the solution can be obtained by working through no more than 27 equations. But are there more elegant ways?

The number theorists have been at work. The Wikipedia entry includes a number of nuggets, including a lower bound of 17 clues to determine a valid puzzle, and a reassurance that the puzzle composers will not lack for work, with 21 orders of magnitude (6.67x10²¹) possible solutions, although this includes rotations and transpositions of other solutions, and experienced puzzle solvers will probably pick up patterns that will enable them to quickly solve the rotations and transpositions. There is an algorithm available to a puzzle composer that will check for the existence and uniqueness of a solution given the 17 or more clues the puzzle-writer provides.

But that elusive solution algorithm ... not yet?

How many Sudoku solutions exist for each n? To put the question another way: Starting from a blank grid—with no givens at all—how many ways can the pattern be completed while obeying the Sudoku constraints? As a first approximation, we can simplify the problem by ignoring the blocks in the Sudoku grid, allowing any solution in which each column and each row has exactly one instance of each number. A pattern of this kind is known as a Latin square, and it was already familiar to Leonhard Euler more than 200 years ago.

Perhaps just as well. Suppose we could reduce all Su Doku to linear algebra problems. We could teach them in the eighth grade, and perhaps rob the puzzle of all its play value.

When you lay down your pencil on a completed Sudoku, the thought that you've just dispatched a problem in the class NP may boost your psychological wellbeing, but the NP label doesn't say anything about the relative difficulty of individual Sudoku puzzles. For that, a different kind of hierarchy is needed.

Quite.