Brian Hayes in American Scientist:
A few years ago, if you had noticed someone filling in a crossword puzzle with numbers instead of letters, you might well have looked askance. Today you would know that the puzzle is not a crossword but a Sudoku. The craze has circled the globe. It’s in the newspaper, the bookstore, the supermarket checkout line; Web sites offer puzzles on demand; you can even play it on your cell phone.
Just in case this column might fall into the hands of the last person in North America who hasn’t seen a Sudoku, an example is given on the opposite page. The standard puzzle grid has 81 cells, organized into nine rows and nine columns and also marked off into nine three-by-three blocks. Some of the cells are already filled in with numbers called givens. The aim is to complete the grid in such a way that every row, every column and every block has exactly one instance of each number from 1 to 9. A well-formed puzzle has one and only one solution.
The instructions that accompany Sudoku often reassure the number-shy solver that “No mathematics is required.” What this really means is that no arithmetic is required. You don’t have to add up columns of figures; you don’t even have to count. As a matter of fact, the symbols in the grid need not be numbers at all; letters or colors or fruits would do as well. In this sense it’s true that solving the puzzle is not a test of skill in arithmetic. On the other hand, if we look into Sudoku a little more deeply, we may well find some mathematical ideas lurking in the background.
Caption: Sudoku puzzles have to be filled in so that each number appears exactly once in each column, each row and each of the blocks delineated by heavier lines. The order-1 puzzle is a trivial 1×1 grid; the order-2 Sudoku is a 4×4 grid to be filled with integers from 1 to 4; the order-3 puzzle is a 9×9 grid where the allowed numbers are 1 through 9. Some useful terminology: The individual compartments are cells; the nxn groups of cells are blocks; the cells are arranged in horizontal rows and vertical columns; the blocks likewise are organized in horizontal bands and vertical stacks; the union of a cell’s row, column and block is called its neighborhood; the numbers supplied in the initial state are givens. The order-3 Sudoku shown here is a variation on the very first puzzle published, in 1979 in Dell Pencil Puzzles & Word Games; by present-day standards it is quite easy. Cells marked in blue are fully determined by the givens alone.
More here.