# Puzzle Description

A Sudoku puzzle has 9 **rows**, identified as "A"
through "I", and 9 **columns**, numbered 1 through 9. There are 81 **cells** which are
grouped into 9 **boxes**, numbered 1 through 9. Each cell may contain a number from
one to nine, and each number can only occur once in each row, column and box.

It is helpful to use the term **line** to indicate either a row or a column,
and **unit** to indicate a row, column, or box. A **candidate value** refers
to a possible value for an unknown puzzle cell. A sample puzzle is shown in the
next section.

A Mega Sudoku puzzle has 16 rows, 16 columns, 256 cells and 16 boxes. These puzzles can be very challenging.

Wikipedia has entries for Sudoku, Glossary of Sudoku and more.

# Sudoku Solution Strategies

## Strategy Descriptions

* Related Values Chaining, Tree Chaining*, and several
*Chaining Methods* for solving Sudoku puzzles are described.
The foundation for these is chaining, also called xy-chaining. A chain is a series of
*related* two-valued cells that are linked together. *"related"* means that
two linked cells have a (one or both) common candidate value and share the same row,
same column and/or same box.

Additionally non-chaining Solution Strategies named *BigFish*
are described in Appendix A.

*Related Values Chaining * extends xy-chaining to
analyze row-, column- and box- interactions between chain links and cells that are not
part of the chain. A group of two or more chains are considered, depending on the
Chaining Method used. Related values analysis can**:**

- solve puzzle cells that are not links in the chain
- determine additional cells that can be used as chain links, leading to longer chains

*Tree Chaining* extends xy-chaining for multiple branches and incorporates
Related Values Chaining. A "Chain Tree" is a multi-branched chain.

Each *Chaining Method* is a front end to chaining
utilizing special treatment for the first one or two cells in the chain, and
allowing a three-, four- or five- valued cell for the chain head. The Chaining
Methods are used with Related Values Chaining and Tree Chaining.
The Methods are**:**

- Two-valued Diamond Chaining
- Six values Diamond Chaining
- Three values Chaining
- Four values Chaining
- Five values Chaining

The *BigFish Strategies* don't use chaining. They consider a single candidate
value and look for a
pattern across sets of four, nine, sixteen or twenty-five cells. If the pattern
is matched the candidate value can be removed from certain related cells.

### Applicability

These solution strategies are applicable equally to traditional 9 x 9 Sudoku puzzles and Mega Sudoku 16 x 16 puzzles. The strategies range from simple to complex. Most are only necessary for diabolical (difficult) sudoku puzzles. A few are not practical for manual (paper and pencil) use - for these computer processing is envisioned.

## A difficult puzzle

Col 1 | Col 2 | Col 3 | Col 4 | Col 5 | Col 6 | Col 7 | Col 8 | Col 9 | |||
---|---|---|---|---|---|---|---|---|---|---|---|

Row A | . | . | . | 8 | . | . | . | 2 | . | ||

Row B | . | . | . | . | 3 | . | . | . | 7 | ||

Row C | . | . | . | . | 9 | 1 | 3 | . | . | ||

Row D | 6 | . | 8 | 2 | . | . | . | . | . | ||

Row E | . | 4 | . | . | . | . | . | 6 | . | ||

Row F | . | . | 1 | . | . | . | . | . | 5 | ||

Row G | 4 | 6 | . | . | . | . | . | . | . | ||

Row H | . | . | 7 | . | . | . | . | . | 9 | ||

Row I | . | 8 | 9 | . | 1 | 7 | . | . | . |

The value for the cell "row A, column 1" is unknown and is shown as "**.**"; the
value for cell "A-4" is **8**.

The first box contains cells A-1, A-2, A-3, B-1, B-2, B-3, C-1, C-2 and C-3.

"**.**" indicates an unsolved (unknown) cell.

Click to Display Solution

# Related values for Chaining

## Three row partly-solved puzzle subset

This puzzle subset is used for the examples for Related Values. The chain head is cell C-9 and for the first chaining pass it is assumed to be 2. The chain links from cell C-9 to cell A-8 and on to A-4.

For the second chaining pass the head cell is assumed to be 4. The chain links from C-9 to C-7 and on to A-8.

## Related Values Description

A Chaining Related Value is the value that a cell will have if the chain involved agrees with the solution to the puzzle.

For a two-valued puzzle cell two chains may be analylzed, one for the cell's smaller candidate value and the other for the cell's larger candidate value. Initially it is unknown which chain will be "true" - will agree with the solution to the puzzle. For each of the two possible chains a set of Chaining Related Values can be developed. Each set of related values should be a table sized the same as the sudoku puzzle (9 rows, 9 columns and 81 cells). Initially all of the related values are unknown (may be blank or zero). During chaining related values will be determined and put into the table.

A cell with a known value before chaining is not involved in related values analysis.

The first step is to put the assumed value for the chain head into the related values table. When a chain link is determined, the link value (the value for the cell for chaining) is put into the table. As described in the following section additional related values may be determined and put into the table. Note that the related values tables are not a copy of the puzzle cell values.

For every cell there are three groups of directly related cells, those in the same row, the same column or the same box. This consideration is important for related values.

Refer to the example puzzle subset above. During chaining consider a cell of interest, say cell A-1, with candidate values 1, 4 and 9. The following analysis can be performed :

- If any other cell in Row A has a related value that is 1, 4 or 9, then that candidate can't be true for cell A-1 for the chain being performed.
- If any other cell in Column 1 has a related value that is 1, 4 or 9, then that candidate can't be true for cell A-1 for the chain being performed.
- If any other cell in the containing box has a related value that is 1, 4 or 9, then that candidate can't be true for cell A-1 for the chain being performed.

For example : suppose that during chaining Cell A-1 has candidate values 1, 4 and 9, and cell A-8 is known to have a related value of 1, and cell C-1 is known to have a related value of 9. We can assign a chaining related value of 4 for Cell A-1 for the chain.

__Possibility of Solution__

There is a possible big payoff for the related values analysis**:** related
values may be determined for all unknown cells.
When this occurs the puzzle is solved, that is the chaining being performed
assumed a value for the chain head which leads to the solution to the puzzle
("the chain is tue"). **Each related value solves the corresponding puzzle
cell.**

__Analyzing the chains for both passes__

A more likely, smaller, benefit is that one or more corresponding cells in the
two tables have the same value.
This means that no matter which of the two possible values the chain head
takes on, the related value solves the corresponding puzzle cell. **The
puzzle cell should be set to the related value.** Note that the cell solved is not
part of the chain, is not a chain link. As more chains are
analyzed, more and more cells may be solved.

__Related Values Determination and Longer Chains__

A detailed example of related values determination is presented in the next section.
Extended logic for additional chain links and longer chains is described separately in
the section *Longer chains with Related Values*.

### Related Values Chaining Example

This example uses the partly-solved puzzle subset shown above. For the chain head, cell C-9, two chains will be analyzed with a description of chaining related values. Pass 1 is for the chain starting with the cell's smaller candidate value, and Pass 2 is for the chain starting with the cell's larger candidate value.

__Example Pass 1__

The chain head is cell C-9, and is assumed to be 2. The chain links from cell C-9 to cell A-8 and on to A-4. For this three-cell chain we have these Considerations for related values:

- cell C-9 is assumed to be 2 and is assigned Related Value 2
- consequently cell A-8 would be 1 and is assigned Related Value 1
- cell A-4 would be 5 and is assigned Related Value 5
- the cells in row C other than C-9 may not have 2 as a candidate value
- cells in row A other than A-4 and A-8 may not have value 1 or 5
- cells in column 9 other than C-9 may not have 2
- cells in column 8 other than A-8 may not have 1
- cells in column 4 other than A-4 may not have 5
- cells in the third box other than C-9 and A-8 may not have have 1 or 2
- cells in the second box other than A-4 may not have 5

##### Additional related values, part 1

- Consideration (2) above has an implication for cell A-2 - it is now the only cell in row A that can take on candidate value 2 for the puzzle solution when the chain is true. So the related value for the cell is set to 2. As cell A-2 is not a link of the chain, this consideration is additional information that may help solve the puzzle.
- Consider (5) above regarding cell A-5 - the cell's candidates are 1, 5 and 9 so the related value for the cell is set to 9.
- Consider (9) above regarding cell C-7 - the cell's candidates are 1 and 4 so the related value for the cell is set to 4.

The additional related value considerations for part 1 are:

- cell A-2 is assigned Related Value 2
- cell A-5 is assigned Related Value 9
- cell C-7 is assigned Related Value 4
- the cells in row A other than A-2 and A-5 may not have 2 or 9 as candidate values (related to (5) above)
- cells in row C other than C-7 may not have 4 (related to (4) above)
- cells in column 2 other than A-2 may not have 2
- cells in column 5 other than A-5 may not have 9
- cells in column 7 other than C-7 may not have 4
- cells in the first box other than A-2 may not have 2
- cells in the second box other than A-5 may not have 9 (related to (10) above)
- cells in the third box other than C-7 may not have 4 (related to (9) above)

##### Additional related values, part 2

- Consider both (5) and (14) above regarding cell A-1 - the cell's candidates are 1, 4 and 9, so the chaining related value for the cell is 4.

The related value considerations can be extended to include:

- cell A-1 is assigned Related Value 4
- the cells in row A other than A-1 may not have 4 as a candidate value (related to (5) above)
- cells in column 1 other than A-1 may not have 4
- cells in the first box other than A-1 may not have 4 (related to (19) above

Here are the seven chaining related values shown in a puzzle grid. The cells that are
known for the example are indicated with an "*****" character.

**Related values for pass 1,** cell C-9 = 2

Col 1 | Col 2 | Col 3 | Col 4 | Col 5 | Col 6 | Col 7 | Col 8 | Col 9 | |||
---|---|---|---|---|---|---|---|---|---|---|---|

Row A | 4 | 2 | * | 5 | 9 | * | * | 1 | * | ||

Row B | * | * | * | * | * | * | |||||

Row C | * | * | * | 4 | * | 2 |

__Example Pass 2__

This is the second chain for head cell C-9. The chain head, cell C-9, is assumed to be the cell's larger value, 4. The chain links from cell C-9 to cell C-7 and on to A-8.

For this chain we have these Considerations for related values:

- cell C-9 is assumed to be 4 and is assigned Related Value 4
- cell C-7 would be 1 and is assigned Related Value 1
- cell A-8 would be 2 and is assigned Related Value 2
- the cells in row C other than C-9 and C-7 may not have 1 or 4 as a candidate value
- cells in row A other than A-8 may not have 2 as a candidate value
- cells in column 9 other than C-9 may not have the value 4
- cells in column 7 other than C-7 may not have 1
- cells in column 8 other than A-8 may not have 2
- cells in the containing box other than C-9, C-7 and A-8 may not have 1, 2 or 4

##### Additional related values, part 1

- Consideration (4) above has an implication for cell C-1 - the cell's candidates are 1 and 9 so the chaining related value for the cell would be 9. This consideration may help solve the puzzle.
- Consider (5) above regarding cell C-2 - it is now the only cell in it's box with a candidate value of 2, so the related value for the cell is set to 2.

The additional related value considerations for part 1 are:

- cell C-1 is assigned Related Value 9
- cell C-2 is assigned Related Value 2
- the cells in row C other than C-1 and C-2 may not have 2 or 9 as candidate values (related to (4) above)
- cells in column 1 other than C-1 may not have the value 9
- cells in column 2 other than C-2 may not have 2
- cells in the first box other than C-1 and C-2 may not have 2 or 9

##### Additional related values, part 2

- Consider (15) above regarding cell A-5 - it is now the only cell in it's row with a candidate value of 9, so the related value for the cell would be 9.
- Now consider cell A-4 - the only cell in it's row with a candidate value of 5, so the related value for the cell would be 5.
- Consider both (4) and (12) above regarding cell C-5 - the cell's candidates are 1, 8 and 9, so the related value for the cell would be 8.
- Now consider cell B-5, which has candidates 1 and 8, so the related value would be 1.
- Consider cell B-1, which has candidates 1 and 3, the related value would be 3.
- Consider cell B-2, which has candidates 1, 3 and 8, the related value would be 8.

The related value considerations can be extended to include:

- cell A-5 is assigned Related Value 9
- cell A-4 is assigned Related Value 5
- cell C-5 is assigned Related Value 8
- cell B-5 is assigned Related Value 1
- cell B-1 is assigned Related Value 3
- cell B-2 is assigned Related Value 8
- the cells in row A other than A-4 and A-5 may not have 5 or 9 (related to (5) above)
- cells in row B other than B-1, B-2 and B-5 may not have 1, 3 or 8
- cells in row C other than C-5 may not have 8 (related to (4) and (12) above
- cells in column 1 other than B-1 may not have 3 (related to (13) above)
- cells in column 2 other than B-2 may not have 8 (related to (14) above)
- cells in column 4 other than A-4 may not have 5
- cells in column 5 other than A-5, C-5 and B-5 may not have 1, 8 or 9
- cells in the first box other than B-1 and B-2 may not have 3 or 8 (related to (15) above)
- cells in the second box other than A-4, A-5, B-5 and C-5 may not have 1, 5, 8 or 9

Here are the eleven related values shown in a puzzle grid. The cells that are
known for the example are indicated with an "*****" character.

**Related values for pass 2,** cell C-9 = 4

Col 1 | Col 2 | Col 3 | Col 4 | Col 5 | Col 6 | Col 7 | Col 8 | Col 9 | |||
---|---|---|---|---|---|---|---|---|---|---|---|

Row A | * | 5 | 9 | * | * | 2 | * | ||||

Row B | 3 | 8 | * | * | 1 | * | * | * | * | ||

Row C | 9 | 2 | * | * | 8 | * | 1 | * | 4 |

**Analyzing both chains**

**Analyzing both chains**

The preceeding sections describe both passes for chaining on the example
puzzle subset. For the two sets of related values there are two corresponding cells
that have the same value. For both values of the chain head the related value for cell
A-4 is 5; and the related value for cell A-5 is 9. **So these two puzzle cells are
solved.** Note that the underlying basic chaining logic didn't solve anything. Refer
to *Related values for cell C-9 = 2* and *Related values for cell C-9 = 4*.

### Longer chains with Related Values

Related values considerations can enlarge the set of chaining link candidates, leading to longer chains. Referring to the example puzzle subset shown below, consider a chain with head cell C-2 having the assumed value of 4.

The chain links on the value 4 from cell C-2 to cell C-9, then links on the value 5 to Cell C-4. The chain has three linked cells.

Now consider cell C-6, which initially has four candidate values, {1, 2, 4, 5}. Using related value considerations, the cell's possible chaining candidates are only the values {1, 2} (the related values of 4 and 5 have been assigned to cells C-2 and C-9). So cell C-6 is a chain link candidate, and we can link on the value 1 from cell C-4 to cell C-6.

As cell C-3 initially had candidate values {1, 2, 3, 4, 5}, it's possible chaining candidates are only the values {2, 3}. So we can link on the value 2 from cell C-6 to cell C-3. Thus we have a chain with five linked cells.

**Example puzzle subset**

Col 1 | Col 2 | Col 3 | Col 4 | Col 5 | Col 6 | Col 7 | Col 8 | Col 9 | |||
---|---|---|---|---|---|---|---|---|---|---|---|

Row A | 1 2 4 5 | 1 2 4 6 8 | 9 | 1 2 5 8 | 1 2 4 8 | 3 | 1 4 5 6 | 1 4 6 | 7 | ||

Row B | 1 3 4 5 | 1 3 4 6 8 | 1 3 4 5 8 | 9 | 1 4 7 8 | 1 4 5 7 8 | 1 4 5 6 | 1 3 4 6 | 2 | ||

Row C | 7 | 3 4 | 1 2 3 4 5 | 1 5 | 6 | 1 2 4 5 | 9 | 8 | 4 5 |

# Tree Chaining

Tree Chaining using Related Values is described using the example puzzle shown below.

## Tree Chaining example subset

For the Chain Tree example the chain head is cell B-8 and is assumed to be **4**.

Col 1 | Col 2 | Col 3 | Col 4 | Col 5 | Col 6 | Col 7 | Col 8 | Col 9 | |||
---|---|---|---|---|---|---|---|---|---|---|---|

Row A | 4 5 | 6 | 3 | 8 | 2 | 1 4 5 | 7 9 | 7 9 | 1 4 5 | ||

Row B | 7 | 4 8 | 5 8 | 1 3 4 5 | 1 3 5 | 9 | 2 | 1 4 | 6 | ||

Row C | 2 | 1 | 9 | 4 5 6 | 5 6 | 7 | 3 | 8 | 4 5 |

## Description of Tree Chaining

A Chain Tree is formed when a cell in a chain links to two or more cells, giving a a multi-branched chain. Chain Trees can have more than two branches.

A Chain Tree can be found in the example puzzle. The chain head is cell B-8, and is assumed to be 4. The chain's first branch links from cell B-8 to cell B-2, then on to B-3 and finally A-1. The second branch links from cell B-8 to C-9 and then to C-5. This chain tree has the following related value considerations:

- cell B-8 is assumed to be 4 and is assigned Related Value 4
- cell B-2 would be 8 and is assigned Related Value 8
- cell B-3 would be 5 and is assigned Related Value 5
- cell A-1 would be 4 and is assigned Related Value 4
- for the second branch, cell C-9 would be 5 and is assigned Related Value 5
- cell C-5 would be 6 and is assigned Related Value 6
- the cells in row B other than B-2, B-3 and B-8 may not have 4, 5 or 8 as candidate values
- cells in row A other than A-1 may not have the value 4
- cells in row C other than C-5 and C-9 may not have 5 or 6
- cells in column 1 other than A-1 may not have 4
- cells in column 2 other than B-2 may not have 8
- cells in column 3 other than B-3 may not have 5
- cells in column 5 other than C-5 may not have 6
- cells in column 8 other than B-8 may not have 4
- cells in column 9 other than C-9 may not have 5
- cells in the first box other than A-1, B-2 and B-3 may not have have 4, 5 or 8
- cells in the second box other than C-5 may not have have 6
- cells in the third box other than B-8 and C-9 may not have have 4 or 5

##### Additional related values

- Considerations (1) and (5) above have an implication for cell A-9 - the cell's candidates are 1, 4 and 5 so it's related value would be 1.
- Considerations (5) and (6) above have an implication for cell C-4 - the cell's candidates are 4, 5 and 6 so it's related value would be 4.
- With these two additional related values determined, there is an implication for cell A-6 - it's candidates are 1, 4 and 5, so it's related value would be 5.

The additional related value considerations are:

- cell A-9 is assigned Related Value 1
- cell C-4 is assigned Related Value 4
- cell A-6 is assigned Related Value 5
- the cells in row A other than A-6 and A-9 may not have the value 1 or 5 (related to (8) above)
- cells in row C other than C-4 may not have 4 (related to (9) above)
- cells in column 4 other than C-4 may not have 4
- cells in column 6 other than A-6 may not have 5
- cells in column 9 other than A-9 may not have 1 (related to (15) above)
- cells in the second box other than A-6 and C-4 may not have 4 or 5 (related to (17) above)
- cells in the third box other than A-9 may not have 1 (related to (18) above)

Here are the 9 related values determined, shown in a puzzle
grid. The cells that are known for the example are indicated with an "*****" character.

**Related values for Chain Tree**

Col 1 | Col 2 | Col 3 | Col 4 | Col 5 | Col 6 | Col 7 | Col 8 | Col 9 | |||
---|---|---|---|---|---|---|---|---|---|---|---|

Row A | 4 | * | * | * | * | 5 | 1 | ||||

Row B | * | 8 | 5 | * | * | 4 | * | ||||

Row C | * | * | * | 4 | 6 | * | * | * | 5 |

Continue with Chaining Methods