Sudoku Helper - Strategies
In what follows a Sudoku Helper solves positions by maintaining a list of possible digits for each unsolved square. A square can be solved immediately if it has only one possibility, or if one of its possible digits cannot be in any other square in the same unit. If no squares can be solved immediately then Sudoku Helper uses four increasingly complicated strategies to try to eliminate possibilities; the following sections describe these strategies.
The rules of Sudoku state that a digit can appear at most once in any unit. Thus, when a square is solved, the digit in that square can be eliminated as a possibility from all other squares in the same row, column or block.
A - If a digit cannot be in two of the horizontal buckets in a row, then it must be in the third, and is therefore not in the other two horizontal buckets in the same block.
- If a digit cannot be in two of the horizontal buckets in a block, then it must be in the third, and is therefore not in the other two horizontal buckets in the same row.
- If a digit cannot be in two of the vertical buckets in a column, then it must be in the third, and is therefore not in the other two vertical buckets in the same block.
- If a digit cannot be in two of the vertical buckets in a block, then it must be in the third, and is therefore not in the other two vertical buckets in the same column.
The pigeonhole principle states that if there are - If a set of
*k*pigeons can only be in*k*pigeonholes, then no other pigeons are in any of these*k*pigeonholes. - If a set of
*k*pigeonholes can only contain*k*pigeons, then no other pigeonholes contain any of these*k*pigeons.
k digits can only appear in k squares
in the unit then we can eliminate all other digits as possibilities in these squares, and if some set of k squares can only contain k digits then we
can eliminate these digits as possibilities in all other squares in the same unit.
In theory the Pigeonhole strategy can be applied with 2 ≤ Special cases of the pigeonhole strategy are known as Hidden/Naked Pairs/Triples/Quads.
Suppose we can prove that one of two squares A, B must contain a digit d is not in A) => (x_{1} is in X_{1})
=> (x_{2} is not in X_{2})
=> …
=> (d is in B)
Four basic rules are used to construct the individual implications in these chains: - If
*d*and*e*are the only possible digits in A, then**(**.*d*is not in A) => (*e*is in A) - If A and B are the only squares in a unit which can contain
*d*, then**(**.*d*is not in A) => (*d*is in B) - If
*d*and*e*are both possibilities of A, then**(**.*d*is in A) => (*e*is not in A) - If A and B are in the same unit and
*d*is a possibility of each, then**(**.*d*is in A) => (*d*is not in B)
. The first, a Generalized Chains, is a sequence of
squares where consecutive squares share a unit, each square has exactly two possibilities, and the sequence of
possibilities is of the form
Chain of Pairsa, b), (b, c), (c, d), …, (x, a)Using rules 1 and 4, if the first square does not contain The second special case is a d. This is a sequence of an even number of squares where consecutive squares
again share a unit, each square has d as a possibility, and for each n ≥ 1 the (2n - 1)^{th} and (2n)^{th} squares
in the sequence are the only two squares in some unit which can contain d. Using rules 2 and 4, if the first square does not contain d, then
the second square does contain d, then the third square does not contain d, etc., giving a chain
of implications that again ends with the last square containing d. Special cases of the Chain of Digits strategy are known
as X-Wing, Swordfish, Guardians, Broken Wings and Turbot-Fish.
Sudoku Helper will always first look for a Chain of Pairs or a Chain of Digits, reporting the smallest chain that it can find. Only if there are
no such chains will it make use of Generalized Chains since these tend to be quite complicated. When Sudoku Helper finds a chain, the hint
will report the chain of |