What Is Sudoku?
Sudoku is a puzzle craze that became popular in Japan in the late 1980's. Sudoku appear in nearly every newspaper and magazine there, much as crossword puzzles do in the United States. More recently, the sudoku craze has swept through England and spread to the Internet. Here's hoping it catches on soon in the United States as well!
A sudoku puzzle is a 9-by-9 grid, divided into nine 3-by-3 regions, with some spaces filled in with digits between 1 and 9. The goal is to fill in the remaining spaces so that each digit appears exactly once in each row, in each column, and in each region. A properly constructed sudoku will have one and only one solution.
At first glance a sudoku puzzle looks very mathematical, but it actually isn't. The numbers 1-9 are used only for convenience—they could easily be replaced by the letters A-I or any other set of nine symbols. Sudoku puzzles are really about logic. Solving a puzzle involves reasoning like “Hmm. 2 can't go here, here, or here, so it must go here.”
In the rest of this document, I'll describe some of the common techniques for solving sudoku. But before reading on, you may want to try your hand at the sample puzzle below. It can be solved using only the techniques described later. (I recommend printing out the puzzle and working in pencil.)
| 5 | 9 | 4 | ||||||
| 1 | 5 | 9 | 6 | 2 | ||||
| 3 | 1 | |||||||
| 4 | 7 | |||||||
|---|---|---|---|---|---|---|---|---|
| 2 | 7 | 1 | ||||||
| 8 | 5 | |||||||
| 3 | 7 | |||||||
| 9 | 5 | 8 | 6 | |||||
| 1 | 8 | 9 |
[Printer-friendly Version]
How to Solve Sudoku
Arthur Conan Doyle once wrote, “[…] when you have excluded the impossible, whatever remains, however improbable, must be the truth.” He would have loved sudoku! The process of elimination is the heart of all sudoku solving, in two different forms: ruling out spaces and ruling out digits.
Ruling Out Spaces
The basic technique in solving sudoku is to look at a region and pick some digit that does not yet appear in that region. Then look at the available spaces in that region and try to rule out spaces where that digit cannot go. If you can rule out all spaces but one, then you know the digit must go in that space.
In its simplest form, ruling out spaces lets you fill in the missing digit when the other eight digits have already been filled in. For example, in the region below, we can fill in the blue space with 7, because all the other digits have already been used in that region.
| 1 | 2 | 9 |
| 5 | 3 | |
| 6 | 8 | 4 |
However, situations like this usually won't arise until you are pretty far along in the puzzle. A more common scenario is shown below.
| 7 | ||||||||
| 8 | 5 | |||||||
| 7 |
In this puzzle fragment, the 7 can't appear in the first or third rows (indicated by red) because those rows already contain 7's. So the 7 must appear in the second row, but two of those spaces are already filled, leaving only the third. The next puzzle fragment illustrates much the same phenomenon, but this time also rules out a column that already contains a 7.
| 7 | ||||||||
| 1 | ||||||||
| 7 | ||||||||
| 7 |
Whenever you see the same digit in two regions that are aligned horizontally or vertically, always check the third region to see if you can fill in the digit in that region as well.
Ruling Out Spaces in Rows and Columns
The basic technique of ruling out spaces can also be applied to rows and columns, as shown in the following puzzle fragment.
| 5 | ||||||||
| 9 | 4 | 8 | 7 | |||||
| 5 | ||||||||
In this example, we can deduce that the blue space must be filled by a 5. The 5 in the second row can't appear in the left region, because that region already contains a 5. And it can't appear in column 6, because that column already contains a 5. The other four spaces in the row have already been filled, leaving only a single space where the 5 can go.
Ruling Out Digits
So far, we have been applying the process of elimination to the spaces where a given digit might go. We can also turn that process around and rule out the digits that might go in a given space, until only one digit remains. For example, consider the following puzzle:
| 8 | ||||||||
| 5 | ||||||||
| 4 | ||||||||
|---|---|---|---|---|---|---|---|---|
| 3 | 9 | 6 | ||||||
| 7 | ||||||||
| 1 | ||||||||
Here, we know that the blue space must be filled by a 2. It can't be a 1, 5, or 8 because those already appear in that column; it can't be a 3, 6, or 9 because those already appear in that row; and it can't be a 4 or 7 because those already appear in that region.
In general, there are twenty other spaces to look at when considering the digits that might go in a given space. For example, if we were trying to figure out what digit goes in the blue space below, we would look at all the digits in the twenty red spaces to see if we can find eight of the nine digits, leaving only a single possible digit for the space in question.
Ruling out digits is usually not very useful at the beginning of a puzzle, but once you've made some progress, be sure to check the intersections of fairly full rows and columns.
Early Warning Signs
The basic techniques described above, ruling out spaces and ruling out digits, are enough to solve many sudoku. For harder puzzles, a few more techniques may be required. I call the next technique early warning signs, because it uses partial information about one digit to “scare off” another digit, before we've completely figured out where the first digit goes.
Here's an example:
| 7 | ||||||||
| 2 | 9 | 8 | 3 | |||||
| 7 |
By ruling out spaces, we can deduce that the 7 in the upper left region must go in one of the two blue spaces, but we don't yet have enough information to know which one. Note, however, that both spaces are in row 3. No matter which space the 7 ends up in, no other 7 can use row 3. In particular, the 7 for the upper right region cannot appear in row 3, which is enough to tell us that that digit must go in the dark blue space below.
| 7 | ||||||||
| 2 | 9 | 8 | 3 | |||||
| 7 |
Here is a more complicated example of this kind of reasoning.
| 1 | 2 | 3 | 4 | 8 | 9 | |||
| 1 | 7 | |||||||
|---|---|---|---|---|---|---|---|---|
| 2 | ||||||||
| 6 | ||||||||
| 8 | ||||||||
| 9 |
Where does the 7 for the top row go? It can't go in the open space in the upper right region, because there is already a 7 in that column. Therefore, the 7 must go in one of the two blue spaces in the upper middle region. Now, where does the 7 for column 4 go? It can't go in the upper middle region, because we just decided that the 7 for that region must go in the top row. Therefore, the 7 for column 4 must go in the dark blue space.
Basically, the idea of early warning signs lets us rule out spaces earlier than we would otherwise be able to. We can also use early warning signs to rule out digits, as shown below.
| 1 | 2 | 3 | 4 | 8 | 9 | |||
| 5 | 2 | 9 | ||||||
| 8 | 1 | 3 | 7 |
Here, we know that the 7 for row 1 cannot appear in column 7, so it must appear in the one of the light blue spaces in columns 5 and 6. Therefore, 7 cannot appear in the dark blue space in the middle region. Coupled with the 5 in the left region, this tells us that the dark blue space must contain a 6.
It's very hard to take advantage of early warning signs without making some kind of marks on your paper. For example, when you are ruling out spaces and you have narrowed a particular digit down to two possible spaces, write a tiny copy of the digit in the bottom corner of the space. If the two spaces are in the same row or column, then you can “claim” that row or column for that digit.
The Pigeonhole Principle
Another advanced technique is based on the pigeonhole principle. Basically, it says that if you've narrowed two different digits down to the same two spaces, then you know that no other digit can possibly appear in those spaces.
| 5 | ||||||||
| 7 | 1 | 8 | 3 | |||||
| 3 | 9 | 2 | 7 | 4 |
Because there are 3's in the second and third rows, the 3 for the top row must appear in one of the light blue spaces. Similarly, because there are 7's in the second and third rows, the 7 for the top row must appear in one of the light blue spaces. By the pigeonhole principle, we can conclude that those two spaces must contain 3 and 7, in some order. Now, what about the 4 for the middle region? It can't appear in the light blue spaces because those belong to 3 and 7. And it can't appear in row 3 because that row already has a 4. Therefore, the 4 must appear in the dark blue space.
Like early warning signs, the pigeonhole principle is easiest to apply if you make small notations in the spaces when you've narrowed a digit down to two possible spaces. If you see notations for the same two digits in the same two spaces, try to use the pigeonhole principle.
If All Else Fails
The technique of last resort is guessing. Keep in mind, however, that the vast majority of sudoku are constructed to be solvable by logic alone, so guessing should almost never be necessary.
The problem with guessing, of course, is that you might guess wrong, so you need to be prepared to recover from bad guesses. Use different colored pencils, or different sheets of paper, or some other system to keep track of which entries are “real” and which are the results of your guess.
Pick a digit that you've narrowed down to two possible spaces or a space that you've narrowed down to two possible digits, and fill one in arbitrarily. Then continue using the techniques above to fill in other digits. Ideally, one of two things will eventually happen. Either you'll solve the puzzle (yay!), or you'll reach an impossible state. An example of an impossible state, in which there is no place to put an 8, is shown below.
| 1 | 5 | ||||
| 8 | |||||
| 6 | 4 | ||||
| 8 | |||||
If you reach an impossible state, then go back to your original decision and make the opposite choice. If you originally picked one of two spaces, then pick the other space now. If you originally picked one of two digits, then pick the other digit now. Except that this time, it's not a guess. Because the first way didn't work out, you know that this way must be correct.
Above, I said that, ideally, one of two things would happen. Unfortunately, there is a third possibility. You might get stuck again. In that case, you might make another guess. However, you will probably be better off throwing away the current guess and picking a different place on the board to make a guess. The alternative is to have several layers of guesses active simultaneously, but that way lies madness (or at least lots of different colors of pencils).
Maintained by Chris Okasaki