Dan Rice's Sudoku Blog

Going Pair-Shaped

The next Sudoku solution rule I'd like to discuss is the rule of pairs.

Suppose we've been keeping track of pencil marks, and find that two cells in the same row, column, or box can both contain exactly the same two values. Recall that if the pencil marks are accurate, this means that these two values are the only possible values that can go in those cells. Since the cells are “related” – they live in the same group (row, column, or box), they can't each contain the same vale. So one cell must contain one of the values from the pair, and the other cell must contain the other value. Why is this important? Because even though we don't know yet which cell contains which value, we can be sure that none of the other cells in the same group (i.e., row, column, or box) can contain either of the values!  We may be able to remove quite a few pencil marks based on this information.

For example, consider the puzzle below:

After performing elimination and finding uniques (pigeonholing), we are faced with this grid:

Take a look at box 9 (the box in the lower-right corner). Notice that two cells in the box contain the pair of values (7, 8). So, we can cross out 7 and 8 from cell (9, 8), and 7 from cells (7, 9) and (9, 9).

Those same two cells also happen to be in the same row, row 7. So we can remove 7s and 8s from row 7, namely the 7 from cell (3,7) and the 8 from cell (6,7).

Here's the new board:

Now there is a new pair: values (1, 4) in cells (9,8) and (9,9). We can remove both values from the rest of box 9 and column 9. Now cell (9,2) has only the value 6 left! We can fill in that value and perform an elimination step:

There is a new pair now, in cells (7,9) and (8,9). In fact, another 22 pencil marks can be removed by the rule of pairs. Finally, we obtain the complete solution:

Hope you enjoyed that! Here are a few grids that can be solved using only the rules I've discussed so far: elimination, uniques, and pairs.

 

 

Unique x 20

The last Sudoku entry discussed the uniqueness rule. As an extreme example, the last 20 clues in this board may be filled in using only this rule. No need to use elimination at all!

Note that the boxes are numbered from 1 at the upper left to 9 at the bottom right.

The solution:

Cell 4,2 is the unique possible location for a 5 in col 4
Cell 6,8 is the unique possible location for a 5 in col 6
Cell 5,2 is the unique possible location for a 1 in box 2
Cell 9,3 is the unique possible location for a 1 in box 3
Cell 1,7 is the unique possible location for a 9 in box 7
Cell 5,8 is the unique possible location for a 8 in box 8
Cell 3,2 is the unique possible location for a 9 in row 2
Cell 2,3 is the unique possible location for a 2 in row 3
Cell 8,7 is the unique possible location for a 4 in row 7
Cell 7,8 is the unique possible location for a 3 in row 8
Cell 1,1 is the unique possible location for a 4 in col 1
Cell 9,9 is the unique possible location for a 5 in col 9
Cell 3,1 is the unique possible location for a 7 in box 1
Cell 7,9 is the unique possible location for a 2 in box 9
Cell 3,4 is the unique possible location for a 8 in col 3
Cell 7,6 is the unique possible location for a 8 in col 7
Cell 8,4 is the unique possible location for a 5 in row 4
Cell 2,6 is the unique possible location for a 4 in row 6
Cell 2,5 is the unique possible location for a 6 in col 2
Cell 8,5 is the unique possible location for a 3 in col 8

The Unbearable Uniqueness of Sudoku

The next simplest rule after the rule of elimination (see the last entry) is uniqueness (another name would be the pigeonhole principle ). This principle says that if there's only one place (the pigeonhole) to put a number (the pigeon), it must go there.

Consider the following puzzle:

The rule of elimination can get us this far:

Here's where the rule of uniqueness comes in. Looking at the pencil marks in the top row, we see that there is only one place for a 6 to go. Since every number must appear somewhere in every row, we know the 6 must go there. Similarly, there is only one place for a 9 to go in the 2nd row, and one place for a 3 in the 5th row.

Filling in these cells, we can perform an additional round of elimination. Some more unique cells pop up, such as the 5 in the 5th row. Earlier, there were two possible places for a 5 in that row, but one of those places was the only place for a 3. Thus, the 5 must belong in the other cell.

Now uniquess gives us a 4 and a 9.  A bit more elimination, and we‘re done!

Process of Elimination

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.

 

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.