Introduction to Sudoku

I'll be posting Sudoku puzzles here regularly. I'll also talk about the program I've written to generate these puzzles. As a programmer, I often find it's more fun to write a program to do something than it is to actually do the thing itself. So rather than spending time solving Sudoku puzzles I've found it more intriguing to try to understand what makes a good puzzle and how to create good puzzles automatically.

Every puzzle I'll post here will have the following properties:

1. The puzzle is a 9×9 grid of cells
2. Every row, column, and highlighted 3×3 box contains each numeral from 1 to 9 exactly once
3. There is a unique solution given the set of numbers revealed in the clue grid
4. The puzzle is solvable using logic alone, without any need for guessing

The last point may bear some further explanation. One way to find the value of a cell would be to make a copy of the puzzle in its current state. Next, make a guess as to the value of the square and continue solving the puzzle. Effectively, you will be using the consequences of the guess to fill in further squares. If at any point you are forced to give up (because there is no legal value to place in a particular square that doesn't violate rule 2), you must undo all the changes stemming from the original guess, returning the the pre-guess copy. Now you can be certain that the guess was not correct.

Conversely, if you manage to finish the puzzle without further guessing, you can be certain the guess was correct (given that rule 3 holds, so the solution must be unique).

Rule 4 says that we never need to use this technique (backtracking in Computer Science terminology). Instead, we can always make progress by a series of logical deductions until the unique solution to the puzzle has been found. For example, given a number in a square in the clue grid, we can eliminate it from all other squares sharing the same row, column, or box. If all possibilities but one have been eliminated from a particular cell, we can fill in the value of the cell and continue.

I'll elaborate on some of the logical rules that can be used in solving puzzles in further blog entries. Others have given colorful names to some of these rules like "X-Wings" and "Swordfish." If you like puzzles that require these kind of rules in their solutions, you‘ve come to the right place.