Puzzles for Programmers and Pros

6.5. Sudoku

I was introduced to Sudoku when my 12-year-old asked me to solve the most challenging one in a book while on a train. Because attempting a solution on a moving train made me slightly sick, I resolved to solve the game by programming. Three hours and 100 lines of programming later, my program could solve the hardest Sudoku puzzles I found on the Web in two seconds. I'm not boasting. The current brevity record for a Sudoku-solving program that I know of is by Arthur Whitney in his programming language q. It's 103 characters long. Now, I do not advocate short program contests, because I think they lead to incomprehensible code, but I do find this impressive.

Let's study Sudoku as an elimination puzzle. The target state is to fill a 9 by 9 grid with digits between 1 and 9. Each digit should appear exactly once in each row, once in each column, and once in each non-overlapping three by three box starting from the upper left corner.

6.5.1. Warm-Up

Consider the following Sudoku puzzle:

Below, we use 0 to represent a blank square.

Let's look at the lower left box in context:

We know that of the five zeroes present in the lower left box, one must be 7 and one must be 8. ...