## The Sudoku Rule

The goal of the Sudoku
game is to
fill the 9x9 grid with the numbers 1 to 9 such that each row, each column
and each 3x3 block does not contain a duplicate number. In other words all these
** regions** must contain all the numbers 1 to 9.

## Solving Sudoku Puzzles

The Sudoku puzzles that you encounter have some pre-filled values and your task is to complete the board according to the Sudoku Rule.

For an empty cell you can mentally try all the numbers 1-9.
The numbers that could potentially be entered are called the candidate values
or just candidates.
If only one number can be entered (i.e. there is only one candidate),
then this number must be the solution value. This simplest solution
strategy is called *(Naked) Single* for obvious reason.

As soon as a value is entered in a cell it can be eliminated safely from all candidates of the cell's row, cell's column and cell's block. So, during the solution process, the number of admissible candidates is steadily decreasing. This Sudoku player performs the elimination of candidates automatically and let you see the remaining candidates.

In addition to the *(Naked) Single* rule there are many
other logical rules to solve Sudoku. In the explanation of these
rules below I will use the term ** region**
to describe rows, columns and 3x3-blocks that all must contain all
the numbers 1-9.

## Solving Strategies

### Naked Singles

If a cell contains only one candidate, then this candidate must be the solution value.

Example:

The cell R4C2 contains only one candidate 2. So, the value of R4C2 must be 2.

### Hidden Singles

If a candidate appears only in one cell of a region, then this candidate is the solution value of the cell.

Example:

In the row 1 (yellow), the candidate 9 appears only in the cell R1C3 (green).
So, the value of R1C3 must be 9.

### Intersections Block/Row or Block/Column (or Locked Candidates)

**Row/Block**

If a row has a candidate common to only one block, then this candidate
will surely be placed there and hence it can be safely removed from
other rows of the block.

Example:

The row 2 (yellow) contains the candidate 2 only inside the top-left block.
So, 2 must be there (green cells) and hence
cannot be in the rest of the block (red). The candidate 2 can be eliminated from the
red cells.

**Block/Row**

If a block has a candidate only in one row, then this candidate
will surely be placed somewhere there and hence it can be safely removed from
the rest of the row.

Example:

The top-right block contains the candidate 9 only in the
row 1. So, 9 must will be placed
in one of the cells R1C8, R1C9
and can be eliminated from the rest of the row 1,
i.e. from the cell R1C2 (red).

**Block/Column and Column/Block**

Analogous rules apply for the intersections of blocks and columns.
For example, the column C7 has the candidate 7 only in the top-right block.
Hence, 7 will surely be placed either in R1C7 or in R3C7, and
therefore can be eliminated from R1C9.

### Naked Pairs

If a region contains 2 cells that together have 2 candidates, then these cells will consume their candidates, and hence these candidates can be removed from the remaining cells of the region.

Example:

In the row 6, the candidates 2 and 9 appear only in the cells R6C1 and R6C6 (green).
These two cells together will consume both candidates. Hence,
the candidates 2, 9 can be removed from other cells of the row,
i.e. from R6C2, R6C3 (red).

### Naked Triples

If a region contains 3 cells that together have 3 candidates, then these cells will consume their candidates, and hence these candidates can be removed from the remaining cells of the region. Note, that the individual cells can have less than 3 candidates.

Example:

In the bottom-right block, the candidates 4, 8, 9 appear only in the
3 cells R7C9, R8C7, R9C9 (green).
These 3 cells together will consume the 3 candidates. Hence,
these candidates 4, 8, 9 can be safely removed from other cells of the block,
i.e. from R7C7, R7C8, R9C8 (red).

### Naked Tuples

The rules Naked Single, Naked Pair and Naked Triple are just a special case of a general Naked Tuple Rule: If N cells in a region contain together exactly N candidates, then they will consume these candidates, and therefore these candidates can be removed from other cells of the region. For N=4, the rule is called obviously Naked Quads.

### Hidden Pairs

Suppose that 2 candidates appear only in 2 cells of a region. So, because these 2 cells together will consume the mentioned 2 candidates, all additional candidates in these cells will surely not be used and can be removed from the 2 cells.

Example:

In the left middle block (yellow), the candidates 3 and 7 appear only
in the 2 cells R4C1 and R6C1 (green).
So, the other candidates 2, 5, 8 can be removed from these cells (R4C1 and R6C1).

### Hidden Triples

Suppose that 3 candidates appear only in 3 cells of a region. So, because these 3 cells together will consume the mentioned 3 candidates, all additional candidates in these cells will surely not be used and can be removed from the 3 cells.

Example:

In the left bottom block (yellow), the candidates 3, 7 and 9 appear only
in the 3 cells R8C1, R9C1 and R9C2 (green).
So, the other candidates 1, 2, 8 can be removed from the green cells.
As you see, it is rather difficult to spot a hidden triple.

### Hidden Tuples

The Hidden Pairs and the Hidden Triple Rules are a special case of the Hidden Tuples Rule. Suppose that N candidates appear only in N cells of a region. So, because these N cells together will consume the mentioned N candidates, all additional candidates in these cells will surely not be used and can be removed from these N cells.

### X-Wing

Let us explain this rule directly by the example on the left. The candidate 9 appear in the row R1 (yellow) only in the 2 cells R1C2 and R1C8 (green). In the row R8 (yellow), the candidate 9 appear also only in 2 cells R8C2 and R8C8 (green). The 4 green cells build corners of a rectangle - they share common columns. In the row R1, either the cell R1C2 or the cell R1C8 will get the value 9. In the row R8, either the cell R8C2 or the cell R8C8 will get the value 9.

Case 1: If R1C2 becomes 9, then R8C2 cannot be 9 and hence R8C8 must be 9.

Case 2: If R1C2 will not be 9, then R1C8 will be 9.
So, R8C8 will not be 9 and hence R1C8 will be 9.

In any case, exactly two diagonal corners of the rectangle will get the value 9 ("X-Wing") and hence eliminate the candidate 9 from the columns C2 and C8. So, 9 can be eliminated from the red cells.

The X-Wing Rule can also be applied to a situation where the roles of rows and columns are interchanged.

### Other Logical Rules

There are many other logical rules for solving Sudoku with imaginative names like:- Color chains
- Swordfish
- XY-Wing
- Multicoloring

### Brute Force and Backtracking

When you cannot apply any logical rule you can always resort to a brute force method of trial and error. However, you should not better use it too extensively - there are just too many possibilities for investigation: 6670903752021072936960.

Nevertheless, you could try brute force with backtracking when a cell contains only few candidates e.g. 2 or 3. You would remember this cell and try the first candidate. When you are lucky you will find the solution. When not, you would undo your moves until you reach the remembered cell and you would try another candidate there. Unfortunately, it can happen that during one trial another cell can become a branching point for investigations and needs to be remembered as well, and so on.