On my most recent plane trip, I finished my books and newspapers and used my computer until its battery ran out. So, I picked up the in-flight magazine and started working on the Sudoku puzzle.

The computer scientist in me has always known that programming a computer to solve a Sudoku puzzle should be fairly easy. Its rules are quite simple and only logic is required to solve it.

I typically took two approaches in solving the puzzle.

• Choose a number and eliminate cells: By far, my preferred approach was to pick a number and use existing constraints to determine in which cell the number must be.
• Choose a cell and eliminate numbers: Rarely, I would take the other approach, which was to pick a cell and use existing constraints to determine which number must go in it.

(I never had to use the hard approach where you guess and then backtrack when your guess turns out wrong.)

In any case, being a contrarian, non-zero-sum kind of guy, I was always more interested in the prospect of generating Sudoku puzzles. So I would think about where, which, and how many numerals to place in a blank grid to make a Sudoku puzzle. I was also cognizant that the puzzle would have to be uniquely solvable—it was no good if there were multiple solutions or if no solution was possible.

On this trip, I realized that solving and generating were linked. When you choose a first number and place it in a blank grid, you can no longer place that number in the same row, column, or three-by-three block. You’ve eliminated that number for those cells. This sounded like the second approach above. For some reason, this insight moved me profoundly. It made me think any puzzle could be solved by taking only that approach. So instead of solving the puzzle, I filled the page with pseudocode implementing the approach.

As soon as I got home, I plugged in the computer and fired up Microsoft Visual Studio. That night and the next day, finding a few minutes at a time here and there, I implemented the algorithm in C#. Here’s how it worked:

1. Start with an empty grid and represent all possibilities for all squares.
2. Initialize the puzzle from the printed page by eliminating all but one possibility for the cells that are known, or certain.
3. For each cell that is certain, eliminate its number as a possibility from the cell's row, column, and block. I referred to this as advancing the puzzle.
4. Assuming additional cells now are certain, repeat the prior step until all cells are certain.

One really interesting thing became clear as I was writing the code. It might seem like you might need a two-dimensional array to represent the cells, but you don’t. All that matters is that each cell be associated with the correct row, column, and block. Each row, column, or block can in fact be represented as an unordered set of cells.

Well, after writing this program, I ran it on the first puzzle in the in-flight magazine. It filled in a few cells as expected and then stopped. This approach alone was not sufficient to solve the puzzle.

After thinking about it for some time, I had insight #2: the puzzle had to be advanced in two ways. The puzzle seemed to require advancing like an inchworm moving first its rear and then its head. So I modified the program as follows:

1. Start with an empty grid and represent all possibilities for all squares.
2. Initialize the puzzle from the printed page by eliminating all but one possibility for the cells that are known, or certain.
3. For each cell that is certain, eliminate its number as a possibility from the cell's row, column, and block. I referred to this as the push part of the advance.
4. For each row, column, or block, if a number is only possible in one cell, then eliminate all other possibilities in that cell. I referred to this as the pull part of the advance.
5. Assuming additional cells now are certain, repeat the prior step until all cells are certain.

This algorithm worked extremely well at solving the Sudoku puzzle. (Update: here is a Zip File of Java Source Code and a Zip File of C# Source Code.) But what about generating one? It was true that you could start with a grid, and put a random number in a random cell. After that, you couldn’t just put any number anywhere, because the first number you placed would limit your choices somewhat, but there would still be lots of possibilities. However, you could keep going until you filled the grid. At what point would you have a puzzle?

Answer: there is a third approach to advancing the puzzle, which is to put a random number in a random cell, constrained only by the cells that are already occupied. This approach can always be used in an empty grid, and may have to be used if the first two approaches can no longer advance the puzzle. Insight #3: puzzles are solved and generated in pretty much the same way.

To generate a puzzle, start with an empty grid and attempt repeatedly to apply the approaches in order. In the beginning, only the third approach will be possible. However, you will reach a point after which the first two approaches will be sufficient to complete the puzzle. That point is, of course, a publishable puzzle.

It turns out that some of the hardest puzzles published do require this third approach. However, I have not tried solving any of them, nor have I modified my program to do so, yet.

Once I realized this, I naturally began to think about minimal and maximal puzzles. A minimal puzzle would be one where a minimum number of cells have been determined using the third approach, and the first two approaches are now sufficient. A maximal puzzle is one where removing even one cell would require solving using the third approach.

A lot of questions remain unanswered. A Google search reveals that people have probably already answered them, but it’s not clear (to me) what the answers are.

• The difficulty of a puzzle is proportional to two things: the number of cells that must be filled, and the number of approaches that must be used. How do you generate a puzzle of a specified difficulty? There are generators that allow you to specify the difficulty, but what exactly do they mean by a named difficulty level ("easy," "hard," "devilish")? Is it an indication of the number of approaches used? I haven't seen the generation algorithms in sufficient detail to know.
• If the third approach must be used for a published puzzle, then does that mean multiple solutions must be possible? Some of the generators do generate puzzles that have multiple solutions. However, I think it is possible to generate a puzzle that requires the third approach, but has only one solution---if you choose the wrong random number/cell, you eventually find out because the puzzle becomes impossible to solve. It may be that your puzzle must require the third approach only once.

It would be cool if you could generate puzzles with a specified number of empty cells requiring the third approach to fill the next cell. You could generate progressively harder puzzles that would teach use of the third approach.