display | more...

Solving Sudoku

The only problem with 18thCandidate's otherwise beautiful writeup is, with just one exception, the entire board can be solved using only the "naked single" technique. The exception is at one point the "hidden single" technique is required. These are the two most elementary methods.

Since you aspire to be a Sudoku grandmaster (and really, who doesn't?), you'll have to learn how to solve difficult puzzles. But before I teach you the secret ways of Sudoku, let's be sure we have our terminology correct.

By the (very few) rules of the game, there are nine rows, nine columns, and nine boxes, each of which must contain the numbers one through nine. For consistency, we'll use 1-based indexing. This means the top row is number one, the bottom row is number nine, and so on.

Here's a little diagram that lists the column, row, and box of each cell. Find the hardlinked cell that says "846" in the right-middle box. "8" means it is in the eighth column, "4" means it is in the fourth row, and "6" means it is in the sixth box.

            col 4
             vvv
*-----------------------------------*
|111 211 311|412 512 612|713 813 913|
|121 221 321|422 522 622|723 823 923| <-- row 2
|131 231 331|432 532 632|733 833 933|
|-----------+-----------+-----------|
|144 244 344|445 545 645|746 846 946|
|154 254 354|455 555 655|756 856 956|
|164 264 364|465 565 665|766 866 966|
|-----------+-----------+-----------|
|177 277 377|478 578 678|779 879 979| <
|187 287 387|488 588 688|789 889 989| < box 9
|197 297 397|498 598 698|799 899 999| <
*-----------------------------------*
                         ^^^^^^^^^^^
                            box 9

Now let's get down to business. If you're at all serious about Sudoku, you'll want to get some software. You could do this all on paper, of course, but I prefer to worry about the logic, not the representation. Some people like to use dots to mark the impossible candidates for a cell (which allows you to solve without needing to erase). I invariably make a mess of it, so I heartily recommend Simple Sudoku, available at http://angusj.com/sudoku/. My favorite feature of the program is the filtering. You can filter so that all the cells that include four as a candidate show up in a pale green. It also includes a hint feature which is very handy for when you play puzzles a difficulty level higher than usual. Naturally it can also generate puzzles of a certain difficulty level (the program has five levels). Its only shortcoming is that it doesn't yet know the highly advanced techniques, but that's okay. When you get to the point where you're learning the highly advanced techniques, you'll know what to do.

A naked single is a cell that has only one candidate. This is by far the most fundamental technique; without it you cannot solve any boards. The Boston Globe, my local newspaper, often prints Sudoku boards that can be solved with nothing more than naked singles, sadly. Here's one such board from April 4th, 2006:

 *-----------*
 |..2|.9.|8..|
 |.1.|736|.5.|
 |4..|2.1|..7|
 |---+---+---|
 |1.9|...|3.6|
 |...|...|...|
 |3.7|...|4.5|
 |---+---+---|
 |8..|3.4|..2|
 |.6.|578|.9.|
 |..1|.2.|5..|
 *-----------*

A hidden single is the only cell in a group that has a certain candidate, and so, must be that candidate. For example, if you have the following setup,

 *-----------*
 |...|...|...|
 |5..|...|...|
 |...|...|...|
 |---+---+---|
 |...|...|5..|
 |...|...|...|
 |...|.5.|...|
 |---+---+---|
 |..5|...|...|
 |...|...|...|
 |...|...|...|
 *-----------*

Then the hardlinked cell at R5C2 must be five, because no other cell in box four can have a five. If you try to put a five anywhere else in the box, there would be a conflict (two fives in a single row or column), scary men with large guns would appear, and you will miss your first (and now last) date with that hip girl from the delicatessen. Here's a puzzle generated by Simple Sudoku that can be solved by naked and hidden singles.

 *-----------*
 |..1|..8|.3.|
 |3.4|.7.|.6.|
 |..7|...|..4|
 |---+---+---|
 |...|8..|..7|
 |.3.|.4.|.8.|
 |1..|..9|...|
 |---+---+---|
 |4..|...|8..|
 |.9.|.2.|1.5|
 |.5.|9..|6..|
 *-----------*

These two techniques are really in a class of their own. With one or two advanced exceptions, these are the only that say, "This cell must be a <certain number>." All of the other techniques narrow down the candidates of cells so that these two techniques may be used.

Now we get to the very interesting techniques. Behind each technique name there should be a writeup describing the method in full, because you certainly aren't expected to learn the technique from the executive summaries of each method given below. If a technique doesn't include a summary here, then that just means it is too complicated to summarize concisely -- it does not necessarily mean the technique is difficult to understand!

These techniques are given in the rough order that I learned them. You may find some later in the list easier to grok than some of the earlier ones. Feel free to learn them out of order; this is merely what I recommend from experience. Techniques in bold are known to have a writeup behind them.

  • naked pair: If two numbers are the only candidates of two cells in a group, then the two numbers can be excluded from the rest of the group.
  • hidden pair: If two numbers are the candidates of only two cells in a group, then the rest of the candidates in those two cells can be excluded.
  • locked candidates
    • locked candidates 1: If a candidate in a box is confined to one line, then the candidate can be excluded from cells on the line outside of the box.
    • locked candidates 2: If a candidate in a line is confined to one box, then the candidate can be excluded from cells in the box not on the line.
  • naked subset: If N numbers are the only candidates of N cells in a group, then the N numbers can be excluded from the rest of the group.
  • hidden subset: If N numbers are the candidates of only N cells in a group, then the rest of the candidates in those N cells can be excluded.
  • X-Wing
  • coloring
  • swordfish
  • XY-Wing
  • XYZ-Wing
  • forcing chains: If all the possibilities of a cell lead to some conclusion, that conclusion must be true.
  • uniqueness test: If a certain action would cause the board to have multiple solutions, then we can assume that action is incorrect.