Sudoku comes from Japan (it originated in the US in 1979, but became popular in Japan after 1984--see article in "Scientific American" cited at the bottom) and is based on what mathematicians call "Latin Squares"--square arrays of numbers in which every number appears exactly once in any row and in any column (different letters, colors or symbols may be used in place of the numbers).

    A Sudoku puzzle contains 9 rows of 9 numbers, each containing (1, 2, 3 ... 9) in a different order, and the same holds for the columns. In addition, however, each Sudoku array can be divided into 9 smaller 3-by-3 squares, each of which which also must contain all the numbers (1,2,3....9). In fact many such arrays exist.

    The challenge of the puzzle is--given just some of the numbers of a specific array, fill in the missing ones, using only logical deduction based on the above requirements.

    The puzzle consists of a square array of 81 cells, which can be divided into 9 columns, (counted from the left), each containing 9 cells. In each column, cells are numbered from the bottom.

    Or else, it can be divided into 9 rows (counted from the bottom), each containing 9 cells. In each row, cells are numbered from the left.

    A notation like 6 (3,2) will mean the number "6" in cell 2 of column 3

    Extra division lines (or darker ones) divide the array into 9 boxes, each with 3 rows of 3 cells each. To define the positions of boxes, it is easiest to classify them by stacks and tiers:

Three boxes in a vertical columns will be called a stack
            (distinguishing left, right or middle stacks)
Three boxes in a horizontal row will be called a tier
            (distinguishing bottom, top or middle tiers)

The requirement of the puzzle:
Every column, row and box must contain all the nine numbers 1,2,3 ... 9.
No number may be repeated, none can be left out.

The same number cannot appear twice in any row, column or box. Therefore, we look for cells whose row, column and box contain between them a wide variety of numbers.
    If that variety includes all numbers except for one, that remaining number is the only choice remaining.

    In principle, it is possible to need to identify unresolved groups of more than two cells. In the case below, two unresolved pairs together help fill another cell in the same box, so that we are really using a group of 4 unresolved cells, arranged in two pairs. Larger unresolved groups make the puzzle more difficult. With a pair, once one of the cells is filled, the other one is also solved, but with larger groups that is no longer true.

Only one choice (OOC) exists here

Only one choice (OOC) exists.

OOC here too. Couldn't have got here without the preceding step!

OOC here too

OOC here too (in the rows)

OOC here too. We are trying to fill the bottom left box.

OC for an 8 in the 3rd row

OC for an 8 in that row. We are on our way to filling the bottom right box.

OOC a 4 in that box.

Last cell left in the box

OOC

OOC

OOC... but here the easy choices have run out.

Therefore, the numbers (1, 3) in that box are an "unresolved pair"--they occupy those cells, but in an unknown order.

Therefore, (6, 8) in that box are another unresolved pair (UP).

With (1,3,6, 8) excluded by unresolved pairs in the box, and (2, 4, 7, 9) disqualified by sharing the same row or column, this is the only choice.

By the above argument, column 4 has a "6" (even though we don't know in which of two cells it is). Therefore "6" must occupy this cell--each adjacent column already includes that number.

    The top box and the bottom box in the middle stack each have two empty cells, in the same row. Taking into account cells with known contents (including unresolved pairs in the top box), these cells must contain either 2 or 4. Two of the cells on top and bottom share the same column, and therefore their numbers must differ. They too, are an unresolved pair. (Each also forms a separate UP with the empty cell to its right, but that is not used right now). In the drawing above, UPs are denoted by two numbers sharing the same cell

    Even if the order of 2 and 4 in the above pair is not known, the remaining two cells in the 4th column must contain 3 and 9. There is already a 3 at (7, 5), so

Next, using SR2 gives [18]. Filling this cell resolves the order of one unresolved pair:

    The "9" in [17] leaves no other choice.

    No other place in this box allows a "3"

    There must exist a "2" in this box and column.
Also, the middle box of the first stack has only one place open for the "6":

from which

---------------------------------
Now consider the two top cells in the left-hand bottom box, (1,3) and (3,3). They must contain the numbers 4 and 5, but in which order? Sometimes a clever observation can tell the correct choice, but at first I found none. The alternative (which is the only way in some devilish puzzles), is to trace the consequences of each choice, and see which one leads to a dead end. Computer programs to solve Sudokus use this approach, but a machine can trace choices much faster than a human.

(Ultimately a better way was found--see here)

    Lets start by trying one of the two possibilities--that in the bottom box,

(1,3) on the left contains "5", and
(3, 3) on the right contains "4".
    This choice makes it possible to complete the entire left-hand stack.


    Illustrated above are two diagrams of the puzzle. On the left is the diagram with all the values available before the guessed choice was made. On the right the guessed values for the top of the bottom-left box

have been added in skinny numerals, and so have all the other choices deduced from them, whose numbering will be distinguished by the letter "A".

    Having placed the "4", we can now complete column 3, and because of the "5" in (4,4), only one choice remains:

The middle box of the first stack has only one place open for the "4":

leaving only one cell open for the "9"

We proceed to the top left box. Somewhere in it must be a "5" and a "6", but these can only be in the middle column--in the two flanking columns, those numbers are already in place, lower down in the puzzle. However, before trying to place them, it helps to examine the right hand top box, which has 4 empty cells--two on the right edge of the puzzle and two on the top edge--and the missing numbers which go there are (1, 5, 6, 8).

    Of these, "5" cannot be on the right edge of the puzzle, because the column along that edge already has a "5" at (9,2). Therefore "5" must go into one of the cells along the top edge, either (7,9) or (8,9). Therefore, no matter which of the two it is, another "5" cannot go into the top row of the left hand top box. This decides our choice in placing the next two numbers: the "6" must go on top, the "5" below it.

(The two remaining cells of the box are easily filled--9 obviously goes into the corner of the puzzle--but are not relevant here).

    The placing of the "6" in the top row resolves the ambiguity of the unresolved pair in (4,9) and (4,8), either of which could hold either a "6" or an "8." Because of [34a], that choice is decided as

It follows that neither 8 nor 6 could go in the top cells of the right-hand top box (anyway, at most one of them could do so, since it was earlier determined that "5" must also be placed there). That forces them into the right side of the box, into cells (9,7) and (9,8).

    And here comes the crunch. Only one free cell remains on the right-hand edge of the puzzle, cell (9,5), and the only number missing in that column is "1." However, that row--row 5--already has a "1" in it, in cell (3,5)!

In the 3 boxes of the middle tier, therefore, the first box has 5 in the top row. The second box already has a 5 (in the bottom), so the third box must have 5 in the middle row. Only one choice:

This leaves only one choice for a "5" in the top right box:

            The remaining cells are relatively easy:

Of the two remaining open cells on the right edge, one must contain a "6". One already has that number in its row, leaving OOC:

The last step resolves an ambiguity

Next, the top row can be completed:

Only one choice for the last cell:

This now resolves an ambiguity on the start of row 6:

[39]     6 (2, 7)     Last empty cell in column 2.
[40]     5 (1, 7)     Last empty cell in column 1.
---------------------------------
[41]     8 (9, 5)     Last empty cell in column 9.
[42]     8 (5, 6)     Last "8" to be placed.
[43]     7 (8, 6)     SR2--all others ruled out.
[44]     4 (3, 6)     Ambiguity removed by step [43].
[45]     7 (3, 4)     Other side of the ambiguity.
[46]     7 (6, 5)

crossing of the only row and and only column that lack a "7".

Last empty cell in row 5. Filling it now helps resolve the several ambiguous pairs of "2" and "4"

[50]     2 (4,2)     Another ambiguous pair
[51]     6 (2, 7)    
[52]     2 (6,4)

    Last numbers in their columns