When I first saw a Sudoko puzzle not long ago, my programming instincts kicked in right away. While some people may use intuition to solve puzzles, my tendency is to try to work out an algorithmic approach — something that‘s guaranteed to work every time, even if only by plodding along.
So, how can a puzzle be solved algorithmically? The key is to make progress towards the solution, one piece of information at a time. What information do we have about a puzzle? Of course we know the values of some of the cells. But even in a cell whose value we don‘t know, we can say that certain values are impossible because they would duplicate the value of another cell in the same row, column, or box. Looking at it the other way, if we know the value of a cell we can use elimination to remove that value as a possibility in all of the cells in the same row, grid, and box.
We can represent the state of our knowledge using pencil marks — little notes in each cell that indicate what values are possible for the cell. Of course, some people may prefer to mark values that have been rejected, or to make other sorts of marks, but I'll stick to marks that show possible values.
Let's solve a relatively easy Sudoku puzzle — one that only requires the rule of elimination. First, the clues:
After performing elimination on all the known values, we have quite a few pencil marks:
For all that work, only two cells now have definite values that didn't previously (namely, the 5 in the upper-left box and the 8 in the center box). Performing elimination using these values gives us the 7 in the upper middle box:
The 7, in turn, allows us to uncover the 3 and 6 in the same box:
Those values allow us to complete two of the boxes:
Continuing, we are to eliminate the 4 from cell (1, 2), leaving only a 1 there. We can remove all the 6's from the upper right box, allowing us to fill it in completely. The 6 in cell (4, 4) allows us to eliminate the 6 in cell (8, 4), which in turn allows us to fill in a 2 there. Removing 2 and 6 from cell (7, 4), we get a 9. Now we can cross out 2 and 9 from cell (1, 4), leaving a 3. Making sure we cross out all the numbers that can be eliminated from the newly solved cells, we get:
The 1 in cell (1, 2) allows us to cross out the 1's in cells (2, 2), (3, 2), and (1, 5). Now we know that (3, 2) must hold a 6 and (2, 2) must hold an 8. The 6 in (3, 2) lets us fill in a 1 in (3, 5) and a 9 in (3, 6).
The 3 in cell (1, 4) lets us eliminate the 3 from cell (1, 7), leaving a 2 there. Crossing out the 2 in cell (1, 5), only a 4 is left. Similarly, eliminating the 3 from cell (1, 7) leaves a 2 there. That 2 can be used to solve cell (2, 8), leaving a 7 there. That 7 allows us to solve cells (7, 8) and (8, 8), placing a 5 and a 6 in those cells, respectively. Now the 7 in cell (2, 8) and the 5 in cell (7, 8) together allow us to cross out everything but the 3 in cell (3, 8). The same 7 in cell (2, 8) also gives us the solution for cell (2, 9).
Crossing out 4's in box 4 lets us complete that box. Box 6 can be solved using the new values in box 4. Now every cell but one each in the upper- and lower-left boxes has been solved, and they can now be solved easily. Finally, we have come up with the solution. It must be unique since every step we took was forced. However, the order in which we took the steps was arbitrary.
Fortunately, not every puzzle can be solved by elimination alone. Next time I'll show how the rule of uniqueness can be put into play.