Deadly Pattern
A deadly pattern is a set of cells whose candidates form a pattern that causes the puzzle to have multiple solutions. Deadly patterns can never be encountered while solving a proper (uniquely-solvable) Sudoku.
If an "almost deadly" pattern (which is a deadly pattern but for the presence of additional candidates) is encountered then at least one of those additional candidates must be correct. This is the basis of various uniqueness tests.
Contents
Definition
Formally, a deadly pattern is a collection of cells and their candidates that ...
- ... have multiple solutions ...
- ... each of which have the same footprint ...
- ... but no (cell,value) pairs in common.
The first two of those points ensure that the puzzle has multiple solutions. The last is a convention to limit the definition to the "core" of the multiple-solutions pattern.
The formal definition is not easy to work with in practice. Simpler descriptions in terms of bivalue cells are used for the commonly-encountered types of deadly pattern, namely Unique Rectangle, BUG and BUG Lite. However, it should be remembered that more complex deadly patterns are also possible in theory.
Examples
A deadly pattern
This is a deadly pattern:
. 12 . | . 21 . | . . . . 23 . | . 32 . | . . . . 31 . | . 13 . | . . .
Its solutions are (reading cells left to right, top to bottom) ...
one solution: .1..2.....2..3.....3..1.... other solution: .2..1.....3..2.....1..3....
... which are easily seen to have the same footprint and be disjoint, as required.
If this pattern occurred whilst solving a Sudoku then we could immediately deduce that the puzzle had multiple solutions.
Inference with an "almost deadly" pattern
This much more interesting scenario is an "almost deadly" pattern due to the presence of additional candidates (shown in blue):
. 12 . | . 213 . | . . . . 123 . | . 32 . | . . . . 31 . | . 13 . | . . .
In this case, the solutions are ...
one solution: .1..2.....2..3.....3..1.... other solution: .2..1.....3..2.....1..3.... third solution: .2..3.....1..2.....3..1....
... which have neither the same footprint nor are disjoint; so the pattern is not deadly.
Without the additional candidates, the pattern would be deadly. Thus, at least one of the additional candidates must be correct. In this particular example, that forces the cells to match the third solution listed above.
An Unavoidable Set in a solution grid is a set of cells whose values can be altered without changing the footprint. A minimal unavoidable set is one that contains no smaller unavoidable sets.
Minimal unavoidable sets and deadly patterns are two views of the same phenomenon, since a deadly pattern can also be regarded as a collection of cells and their candidates all of whose solutions are minimal unavoidable sets.
Thus, we can use the theory of unavoidable sets to state that:
- there are thousands of different types of deadly pattern
- the smallest covers four cells
- the largest covers at least sixty cells (this is probably unusable in practice)
- if there are D(n) types of deadly pattern on n cells then D(4)=1, D(5)=0, D(6)=4, D(7)=0, D(8)=9, D(9)=3, D(10)>46, ...
- all deadly patterns of size less than about 30 cells consist entirely of bivalue cells
Since D(n) is small for n<10, we can catalogue all of the small deadly patterns. For larger deadly patterns, the catalogue is too long to be useful for human players, so rules of thumb involving bivalue cells are used to spot deadly patterns instead.
Catalogue of deadly patterns on <10 cells
In what follows, the candidates are arranged so that either all of the lefthand candidates in each pair are true or all of the righthand candidates are true.
The catalogue is comprehensive up to isomorphism.
4 cells
12 . . | 21 . . | . . . 21 . . | 12 . . | . . . . . . | . . . | . . .
6 cells
12 . . | 21 . . | . . . 21 . . | . . . | 12 . . . . . | 12 . . | 21 . .
12 . . | 23 . . | 31 . . 21 . . | 32 . . | 13 . . . . . | . . . | . . .
12 . . | 21 . . | . . . 23 . . | 32 . . | . . . 31 . . | 13 . . | . . .
12 21 . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . --------- ----------- --------- 21 . . | 12 . . | . . . . 12 . | 21 . . | . . . . . . | . . . | . . .
8 cells
12 . . | 23 . . | 31 . . . 21 . | 32 . . | 13 . . . . . | . . . | . . . --------- ----------- --------- 21 12 . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
12 . . | 21 . . | . . . . 21 . | . . . | 12 . . . . . | 12 . . | 21 . . --------- ----------- --------- 21 12 . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
12 . . | 21 . . | . . . . 21 . | 12 . . | . . . . . . | . . . | . . . --------- ----------- --------- 21 . . | . 12 . | . . . . 12 . | . 21 . | . . . . . . | . . . | . . .
12 . . | 21 . . | . . . . 21 . | 12 . . | . . . . . . | . . . | . . . --------- ----------- --------- 21 . . | . . . | 12 . . . 12 . | . . . | 21 . . . . . | . . . | . . .
12 . . | 21 . . | . . . . 21 . | . 12 . | . . . . . . | . . . | . . . --------- ----------- --------- 21 . . | 12 . . | . . . . 12 . | . 21 . | . . . . . . | . . . | . . .
12 23 . | 31 . . | . . . . . 31 | 13 . . | . . . . . . | . . . | . . . --------- ----------- --------- 21 32 13 | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
12 . . | 24 . . | 41 . . 23 . . | 32 . . | . . . 31 . . | 43 . . | 14 . .
13 24 . | 32 . . | 41 . . 31 42 . | 23 . . | 14 . . . . . | . . . | . . .
12 24 . | 41 . . | . . . 31 43 . | 14 . . | . . . . . . | . . . | . . . --------- ----------- --------- 23 32 . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
9 cells
12 . . | 21 . . | . . . . 23 . | 32 . . | . . . . . 31 | 13 . . | . . . --------- ----------- --------- 21 32 13 | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
12 24 . | 41 . . | . . . 31 . 43 | 14 . . | . . . . . . | . . . | . . . --------- ----------- --------- 23 42 34 | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
12 . . | 21 . . | . . . 23 . . | . . . | 32 . . . 31 . | 12 . . | 23 . . --------- ----------- --------- 31 13 . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .
Deadly patterns in practice
When solving a Sudoku puzzle, there are numerous "recipes" for exploiting (almost) deadly patterns. These techniques differ in the type of deadly pattern being avoided and the positioning or values of the additional candidates.
- Uniqueness Tests. These exploit various arrangements of additional candidates attached to the 4-cell Unique Rectangle.
- BUG (Bivalue Universal Grave). This is the deadly pattern in which all unresolved cells in the whole grid have precisely 2 candidates.
- BUG Lite. This is any deadly pattern in which all cells in that pattern have precisely 2 candidates. The Unique Rectangle and BUG are special cases of BUG Lite.
The corresponding "almost deadly" patterns, in which n cells have additional candidate(s), are called UR n, BUG n or BUG Lite n.
The only type of deadly pattern missing from this categorisation is any with >2 solutions. However, as mentioned previously, such patterns are rare and large, so unlikely to be useful in practice.
External links
- BUG Lite thread on the Sudoku Players' forum
- Pseudo-puzzles thread on the Sudoku Players' forum
See also
 The topic in this article is a still a subject of debate. Parts of the text may not express everybody's opinion. Use the associated Talk page if you do not agree with the opinion of the writer, rather than continuously editing the main article.
|
