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. ...

Get Puzzles for Programmers and Pros now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.