The Solver considers seven strategy types.
Of these, only the first and last actually make moves (and the moves made by the Guess algorithm often have to be retracted). The remaining strategy types simply eliminate candidate moves.
Single Candidature is the most basic of the strategy types - it is so fundamental that the Solver does not offer the option to exclude it. It's possible to solve many Su Doku puzzles by this strategy alone. The solver:
Consider the following puzzle.
. 1 . | . . . | 6 . .
8 4 9 | 2 . . | . . .
. . . | 7 . . | . 9 .
-------+-------+------
. . . | . 6 . | 1 . 9
2 . 1 | . . . | 5 . 8
7 . 8 | . 9 . | . . .
-------+-------+------
. 5 . | . . 8 | . . .
. . . | . . 4 | 9 8 2
. . 3 | . . . | . 1 .
The initial Cell State grid:
3|5 1 2|5|7 | 3|4|5|8|9 3|4|5|8 3|5|9 | 6 2|3|4|5|7 3|4|5|7
8 4 9 | 2 1|3|5 1|3|5|6 | 3|7 3|5|7 1|3|5|7
3|5|6 2|3|6 2|5|6 | 7 1|3|4|5|8 1|3|5|6 | 2|3|4|8 9 1|3|4|5
------------------------------+----------------------------------+-----------------------------
3|4|5 3 4|5 | 3|4|5|8 6 2|3|5|7 | 1 2|3|4|7 9
2 3|6|9 1 | 3|4 3|4|7 3|7 | 5 3|4|6|7 8
7 3|6 8 | 1|3|4|5 9 1|2|3|5 | 2|3|4 2|3|4|6 3|4|6
------------------------------+----------------------------------+-----------------------------
1|4|6|9 5 2|4|6|7 | 1|3|6|9 1|2|3|7 8 | 3|4|7 3|4|6|7 3|4|6|7
1|6 6|7 6|7 | 1|3|5|6 1|3|5|7 4 | 9 8 2
4|6|9 2|6|7|8|9 3 | 5|6|9 2|5|7 2|5|6|7|9 | 4|7 1 4|5|6|7
tells us that the value '3' is the only candidate for the cell (4,2). After that move, the grid is updated to:
3|5 1 2|5|7 | 3|4|5|8|9 3|4|5|8 3|5|9 | 6 2|3|4|5|7 3|4|5|7
8 4 9 | 2 1|3|5 1|3|5|6 | 3|7 3|5|7 1|3|5|7
3|5|6 2|6 2|5|6 | 7 1|3|4|5|8 1|3|5|6 | 2|3|4|8 9 1|3|4|5
------------------------------+----------------------------------+-----------------------------
4|5 3 4|5 | 4|5|8 6 2|5|7 | 1 2|4|7 9
2 6|9 1 | 3|4 3|4|7 3|7 | 5 3|4|6|7 8
7 6 8 | 1|3|4|5 9 1|2|3|5 | 2|3|4 2|3|4|6 3|4|6
------------------------------+----------------------------------+-----------------------------
1|4|6|9 5 2|4|6|7 | 1|3|6|9 1|2|3|7 8 | 3|4|7 3|4|6|7 3|4|6|7
1|6 6|7 6|7 | 1|3|5|6 1|3|5|7 4 | 9 8 2
4|6|9 2|6|7|8|9 3 | 5|6|9 2|5|7 2|5|6|7|9 | 4|7 1 4|5|6|7
whereupon the move (6,2):=6 becomes apparent. The Solver continues along these lines until the following position is achieved:
3 1 7 | . . . | 6 . .
8 4 9 | 2 . . | . . .
6 2 5 | 7 . . | . 9 .
-------+-------+------
5 3 4 | 8 6 . | 1 . 9
2 9 1 | . . . | 5 . 8
7 6 8 | . 9 . | . . .
-------+-------+------
. 5 2 | . . 8 | . . .
1 7 6 | . . 4 | 9 8 2
. 8 3 | . . . | . 1 .
The Cell State grid
3 1 7 | 4|5|9 4|5|8 5|9 | 6 2|4|5 4|5
8 4 9 | 2 1|3|5 1|3|5|6 | 3|7 3|5|7 1|3|5|7
6 2 5 | 7 1|3|4|8 1|3 | 3|4|8 9 1|3|4
------------+------------------------------+-------------------------
5 3 4 | 8 6 2|7 | 1 2|7 9
2 9 1 | 3|4 3|4|7 3|7 | 5 3|4|6|7 8
7 6 8 | 1|3|4|5 9 1|2|3|5 | 2|3|4 2|3|4 3|4
------------+------------------------------+-------------------------
4|9 5 2 | 1|3|6|9 1|3|7 8 | 3|4|7 3|4|6|7 3|4|6|7
1 7 6 | 3|5 3|5 4 | 9 8 2
4|9 8 3 | 5|6|9 2|5|7 2|5|6|7|9 | 4|7 1 4|5|6|7
shows that there is no unfilled cell for which there is just a single candidate value, so each of the nine Number State grids is considered. The Solver finds that the grid for the value '5':
Value 5:
. . . | ? ? ? | . ? ?
. . . | . ? ? | . ? ?
. . 5 | . . . | . . .
----------+----------+---------
5 . . | . . . | . . .
. . . | . . . | 5 . .
. . . | ? . ? | . . .
----------+----------+---------
. 5 . | . . . | . . .
. . . | ? ? . | . . .
. . . | ? ? ? | . . ?
has just a single candidate cell in the Box [3,3], so it makes the move (9,9):=5.
The Solver is able to complete the puzzle by repeated reference to the Cell State grid.
Consider the following puzzle:
. . . | . . 7 | . 9 2
. . . | 8 . 6 | . . .
5 7 . | . . . | . . .
-------+-------+------
. . . | . 1 . | 7 2 .
. . 6 | . 3 . | 1 . .
. 1 4 | . 2 . | . . .
-------+-------+------
. . . | . . . | . 8 6
. . . | 5 . 4 | . . .
9 3 . | 2 . . | . . .
The Single Candidature strategy takes us this far:
6 8 . | . . 7 | . 9 2
. . . | 8 . 6 | . . .
5 7 . | . . 2 | . . .
-------+-------+------
. . . | 6 1 . | 7 2 4
7 2 6 | 4 3 . | 1 5 .
. 1 4 | 7 2 5 | . . .
-------+-------+------
. . . | 9 7 3 | . 8 6
. 6 7 | 5 8 4 | . . .
9 3 8 | 2 6 1 | . . .
but no further. The Cell State grid at this point is:
6 8 1|3 | 1|3 4|5 7 | 3|4|5 9 2
1|2|3|4 4|9 1|2|3|9 | 8 4|5|9 6 | 3|4|5 1|3|4|7 1|3|5|7
5 7 1|3|9 | 1|3 4|9 2 | 3|4|6|8 1|3|4|6 1|3|8
------------------------+------------------+---------------------------
3|8 5|9 3|5|9 | 6 1 8|9 | 7 2 4
7 2 6 | 4 3 8|9 | 1 5 8|9
3|8 1 4 | 7 2 5 | 3|6|8|9 3|6 3|8|9
------------------------+------------------+---------------------------
1|2|4 4|5 1|2|5 | 9 7 3 | 2|4|5 8 6
1|2 6 7 | 5 8 4 | 2|3|9 1|3 1|3|9
9 3 8 | 2 6 1 | 4|5 4|7 5|7
The Solver considers the Number State grid for the value '1':
Value 1: . . ? | ? . . | . . . ? . ? | . . . | . ? ? . . ? | ? . . | . ? ? ----------+----------+--------- . . . | . 1 . | . . . . . . | . . . | 1 . . . 1 . | . . . | . . . ----------+----------+--------- ? . ? | . . . | . . . ? . . | . . . | . ? ? . . . | . . 1 | . . .
and, in particular, Row 7. Clearly, one of the cells (7,1) and (7,3) must contain the value '1', which means that the cell (8,1) doesn't. This leaves the value '2' as the only candidate for the cell (8,1).
In general, the Single Sector Candidates strategy looks through the Number State grids for:
Consider the following position, which is a partial solution of the Swordfish example given later on.
. . 2 | 1 . 5 | 3 7 .
7 . . | 9 . . | . 1 8
6 1 . | . 7 . | . . .
-------+-------+------
. . 8 | . 1 . | 7 . .
. 7 . | . 3 . | . 5 .
. . . | . 2 7 | 4 . .
-------+-------+------
. 6 7 | 4 . 1 | . 3 2
5 . . | . . 6 | 1 4 7
. 4 1 | 7 . . | 9 . .
The Cell State grid is:
4|8|9 8|9 2 | 1 4|6 5 | 3 7 4|6|9
7 3|5 3|4|5 | 9 4|6 2|3 | 2|5|6 1 8
6 1 3|4|5|9 | 2|3|8 7 2|3|8 | 2|5 2|9 4|5|9
----------------------------+----------------------+-----------------------
2|3|4|9 2|3|5|9 8 | 5|6 1 4|9 | 7 2|6|9 3|6|9
1|2|4|9 7 4|6|9 | 6|8 3 4|8|9 | 2|6|8 5 1|6|9
1|3|9 3|5|9 3|5|6|9 | 5|6|8 2 7 | 4 6|8|9 1|3|6|9
----------------------------+----------------------+-----------------------
8|9 6 7 | 4 5|8|9 1 | 5|8 3 2
5 2|3|8|9 3|9 | 2|3 8|9 6 | 1 4 7
2|3|8 4 1 | 7 5|8 2|3 | 9 6|8 5|6
The Solver can't progress with the strategy types described thus far, so it considers Row 9 and notices that the values '2' and '3' are constrained to the cells (9,1) and (9,6). It is certain that these two values will occupy these two cells but it doesn't know in which order. However, it is able to eliminate the value '8' as a candidate for the cell (9,1). Similarly, the Solver considers Column 4 and notices that the values '2' and '3' are constrained to the cells (3,4) and (8,4), which enables it to eliminate '8' as a candidate for the cell (3,4). The eliminations leave the cell (3,6) as the only candidate for the value '8' in Row 3.
In general, the Disjoint Subsets strategy looks for a sector (i.e. a row, column or box) where some subset of values (of size greater than one, of course) is constrained to a set of cells of the same size, whereupon it will eliminate any other candidates from these cells.
Consider the following puzzle:
. . 1 | 8 . . | 6 . .
5 . . | . . . | . . .
. . . | 7 9 . | . . .
-------+-------+------
. 7 3 | . . . | . . .
. 8 . | 9 . 4 | . 1 .
. . . | . . . | 2 9 .
-------+-------+------
. . . | . 1 5 | . . .
. . . | . . . | . . 3
. . 6 | . . 2 | 4 . .
The Single Candidature strategy takes us to:
. . 1 | 8 5 3 | 6 . .
5 . . | 2 4 . | . . .
. . . | 7 9 . | . . .
-------+-------+------
9 7 3 | 1 2 8 | 5 . .
2 8 5 | 9 6 4 | 3 1 7
. . 4 | 5 3 7 | 2 9 8
-------+-------+------
. . . | . 1 5 | . . .
. . . | . . 9 | . . 3
. . 6 | 3 . 2 | 4 . .
at which point the Cell State grid is
4|7 2|4|9 1 | 8 5 3 | 6 2|4|7 2|4|9
5 3|6|9 7|8|9 | 2 4 1|6 | 1|7|8|9 3|7|8 1|9
3|4|6|8 2|3|4|6 2|8 | 7 9 1|6 | 1|8 2|3|4|5|8 1|2|4|5
----------------------------+----------------+-----------------------------
9 7 3 | 1 2 8 | 5 4|6 4|6
2 8 5 | 9 6 4 | 3 1 7
1|6 1|6 4 | 5 3 7 | 2 9 8
----------------------------+----------------+-----------------------------
3|4|7|8 2|3|4|9 2|7|8|9 | 4|6 1 5 | 7|8|9 2|6|7|8 2|6|9
1|4|7|8 1|2|4|5 2|7|8 | 4|6 7|8 9 | 1|7|8 2|5|6|7|8 3
1|7|8 1|5|9 6 | 3 7|8 2 | 4 5|7|8 1|5|9
and the Number State grid for the value '9' is
Value 9:
. ? . | . . . | . . ?
. ? ? | . . . | ? . ?
. . . | . 9 . | . . .
----------+----------+---------
9 . . | . . . | . . .
. . . | 9 . . | . . .
. . . | . . . | . 9 .
----------+----------+---------
. ? ? | . . . | ? . ?
. . . | . . 9 | . . .
. ? . | . . . | . . ?
The Solver considers Rows 1 and 9, each of which has two candidate cells, and notes that, when the value '9' appears in the cell (1,2), it cannot appear in (1,9) or (9,2). Since it cannot appear in (9,2), the value must appear in (9,9). Similarly, when the value '9' appears in (1,9), it cannot appear in (1,2) or (9,9). Since it cannot appear in (9,9), the value must appear in (9,2). The Solver deduces that the value '9' must appear in the cells (1,2) and (9,9) or the cells (9,2) and (1,9). Whichever way the values are arranged in the final solution, the Solver is able to eliminate '9' as a candidate for the cells (2,2), (7,2), (2,9) and (7,9), which leaves the value '1' as the sole candidate for the cell (2,9).
In general, the X-Wing strategy looks for a pair of two-candidate sectors such that a given value is certain to appear in opposing corners, which enables it to eliminate candidates from the connecting sectors. Wayne Gould of Pappocom coined the name X-Wings, because he felt the pattern of eliminations suggested the shape of an X-Wing fighter from Star Wars. However, I think he might have confused his intergalactic battlecraft, because I reckon the pattern forms the shape of an Imperial Tie-Fighter.
The Swordfish strategy type generalizes X-Wing to allow legs of any odd length. So long as the odd-length condition is satisfied, it is certain that exactly one of the leg end-points will contain the given value and the underlying X-Wing logic will still hold true.
Consider the following puzzle.
. . 2 | . . 5 | 3 7 .
7 . . | 9 . . | . . 8
6 1 . | . . . | . . .
-------+-------+------
. . 8 | . 1 . | . . .
. 7 . | . 3 . | . 5 .
. . . | . 2 . | 4 . .
-------+-------+------
. . . | . . . | . 3 2
5 . . | . . 6 | . . 7
. 4 1 | 7 . . | 9 . .
The Single Candidature, Single Sector Candidates and Disjoint Subsets strategy types take us this far:
. . 2 | 1 . 5 | 3 7 .
7 . . | 9 . . | . 1 8
6 1 . | . 7 8 | . . .
-------+-------+------
. . 8 | . 1 . | 7 . .
. 7 . | . 3 . | . 5 .
. . . | . 2 7 | 4 . .
-------+-------+------
. 6 7 | 4 . 1 | . 3 2
5 . . | . . 6 | 1 4 7
. 4 1 | 7 . . | 9 . .
whereupon the Cell State grid is
4|8|9 8|9 2 | 1 4|6 5 | 3 7 4|6|9
7 3|5 3|4|5 | 9 4|6 2|3 | 2|5|6 1 8
6 1 3|4|5|9 | 2|3 7 8 | 2|5 2|9 4|5|9
----------------------------+--------------------+-----------------------
2|3|4|9 2|3|5|9 8 | 5|6 1 4|9 | 7 2|6|9 3|6|9
1|2|4|9 7 4|6|9 | 6|8 3 4|9 | 2|6|8 5 1|6|9
1|3|9 3|5|9 3|5|6|9 | 5|6|8 2 7 | 4 6|8|9 1|3|6|9
----------------------------+--------------------+-----------------------
8|9 6 7 | 4 5|8|9 1 | 5|8 3 2
5 2|3|8|9 3|9 | 2|3 8|9 6 | 1 4 7
2|3 4 1 | 7 5|8 2|3 | 9 6|8 5|6
and the Number State grid for the value '2' is
Value 2:
. . 2 | . . . | . . .
. . . | . . ? | ? . .
. . . | ? . . | ? ? .
----------+----------+---------
? ? . | . . . | . ? .
? . . | . . . | ? . .
. . . | . 2 . | . . .
----------+----------+---------
. . . | . . . | . . 2
. ? . | ? . . | . . .
? . . | . . ? | . . .
The Solver notices that there are several sectors (i.e. rows, columns or boxes) with two possible candidate positions - in particular: Column 8, Column 4, Row 8 and Column 2. The last three of these, when strung together, form a leg, exactly one of whose end-points (the cells (3,4) and (4,2)) must contain the value '2'. The Solver deduces that the value '2' must appear in the cells (3,8) and (4,2) or the cells (3,4) and (4,8). Whichever way the values are arranged in the final solution, the Solver is able to eliminate the value '2' as a candidate for the cells (3,7) and (4,1), which leaves the value '5' as the sole candidate for the cell (3,7).
The long sequences of two-candidate rows, columns and boxes are called 'strings' in the Solver source code. I see two wings - an upper wing and a lower wing - separated by struts, which resembles an old biplane. The presence of strings reminded me of the expression 'Flying Stringbag' - the nickname for the venerable Fairey Swordfish - hence the name given to this strategy type.
The Nishio strategy type is a special type of guess, named after Nishio-san, a Japanese Su Doku guru. Consider the following puzzle:
. 2 . | . . . | 4 . .
. . . | . . . | . 8 .
. . . | 9 1 . | . 5 .
-------+-------+------
9 . . | . . . | 6 . .
7 . . | 5 . 6 | . . 3
. . 1 | . . . | . . 7
-------+-------+------
. 5 . | . 7 3 | . . .
. 4 . | . . . | . . .
. . 8 | . . . | . 2 .
The existing strategy types take us to the point:
. 2 . | . . . | 4 7 .
. . . | . . . | . 8 6
. 7 6 | 9 1 . | 3 5 2
-------+-------+------
9 3 . | . . . | 6 4 .
7 8 4 | 5 9 6 | 2 1 3
. 6 1 | . . . | . 9 7
-------+-------+------
. 5 . | . 7 3 | . 6 .
6 4 7 | . . . | . 3 .
3 . 8 | . . . | 7 2 .
where the Cell State grid is:
1|5|8 2 3|5|9 | 3|6|8 3|5|6|8 5|8 | 4 7 1|9
4|5 1|9 3|5 | 2|3|4|7 2|3|4|5 2|4|5|7 | 1|9 8 6
4|8 7 6 | 9 1 4|8 | 3 5 2
--------------------+------------------------------+---------------------
9 3 2|5 | 1|2|7|8 2|8 1|2|7|8 | 6 4 5|8
7 8 4 | 5 9 6 | 2 1 3
2|5 6 1 | 2|3|4|8 2|3|4|8 2|4|8 | 5|8 9 7
--------------------+------------------------------+---------------------
1|2 5 2|9 | 1|4|8 7 3 | 1|8|9 6 1|4|8|9
6 4 7 | 1|2|8 2|5|8 1|2|5|8|9 | 1|5|8|9 3 1|5|8|9
3 1|9 8 | 1|4|6 4|5|6 1|4|5|9 | 7 2 1|4|5|9
and the Number State grids for the values '1' and '9' are:
Value 1:
? . . | . . . | . . ?
. ? . | . . . | ? . .
. . . | . 1 . | . . .
----------+----------+---------
. . . | ? . ? | . . .
. . . | . . . | . 1 .
. . 1 | . . . | . . .
----------+----------+---------
? . . | ? . . | ? . ?
. . . | ? . ? | ? . ?
. ? . | ? . ? | . . ?
Value 9:
. . ? | . . . | . . ?
. ? . | . . . | ? . .
. . . | 9 . . | . . .
----------+----------+---------
9 . . | . . . | . . .
. . . | . 9 . | . . .
. . . | . . . | . 9 .
----------+----------+---------
. . ? | . . . | ? . ?
. . . | . . ? | ? . ?
. ? . | . . ? | . . ?
The Solver notes that the moves (7,7):=1 or (9,9):=1 would make it impossible to place the remaining '1's, while the move (7,7):=9 would make it impossible to place the remaining 9s. The eliminations leave the value '8' as the sole candidate for the cell (7,7).
In general, the Nishio strategy type eliminates moves that would make it impossible to replace the remaining instaces of the given value. The strategy is essentially a form of guess, as it assumes a move and performs reductio ad absurdum. However, it is a particularly straightforward form of guess that could conceivably be performed by a human.
Sometimes no single candidate move will exist, even after all of the strategy types mentioned above have been tried. In this case the solver will 'guess', i.e. it will assume a candidate move to be correct and proceed until (possibly) a contradiction is found, at which point the solver will revert to the point of guess and try a different candidate move. Many people quite reasonably consider the guess to be an inelegant manner in which to solve a Su Doku. Most composers endeavour to set puzzles that will not require a guess in order to be solved.
When several candidate moves exist, the Solver locates the cell or sector (i.e. row, column or box) with the smallest number of associated candidate moves. When there are several moves with the same lowest number of candidates (usually two), the Solver refers to the Neighbourhood State grid and chooses the move with the lowest score.