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.

 

Comments

[Kit Winterer]

I don't get how you get the 'one' in the upper left box. . . 'Continuing' just doesn't tell me how the '8' got eliminated for that cell.

[Daniel Rice]

Hi Kit -

I've added some more text to help clarify things. The 1 on the upper left box can be written in because we can simply eliminate all the other possibilities based on numbers in the same row, column, and box.

[Ed]

Hi Dan,

I'm trying to understand the logic you used that allowed you to place the 7 in the upper middle box after you placed the pencil marks. (3rd graphic) Will you elaborate for me please?

[Daniel Rice]

Hi Ed -

Let's look at that cell (cell (6,3), in the corner of the upper middle box). When we start the puzzle, we can see that it can't hold a 1,2,3,4,5,6 or 9, because all of those values exist in row 3, in column 6, or in other cells of the upper middle box. Only 7 and 8 are left as possible values.

Now look at cell (6, 6) (in the middle box). Just looking at row 6, column 6, and the other cells in the middle box, we can rule out every number except 8. So we know an 8 must go there.

Now if we revisit cell (6, 3), we can cross out 8 as a possibility since we have found the 8 in column 6. Since only 7 and 8 were possible values, we know that there must be a 7 there.

Hope this helps!

Dan

[eric]

You might want to backtrack and correct your spelling of sudokU in your first sentence, not sudokO. I know it's minor, but the same way a computer programmer might get picky about code, a Japanese speaker is picky about the usage of Japanese words... especially when so many people mispronounce it so many different ways.
I am enjoying the blog otherwise, keep up the good work!

[eric]

You might want to backtrack and correct your spelling of sudokU in your first sentence, not sudokO. I know it's minor, but the same way a computer programmer might get picky about code, a Japanese speaker is picky about the usage of Japanese words... especially when so many people mispronounce it so many different ways.
I am enjoying the blog otherwise, keep up the good work!

[marc]

I found this website easy to trace step by step.