Mirrored from Sudopedia, the Free Sudoku Reference Guide

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.

It is a matter of debate as to whether a Sudoku must have a unique solution. See Uniqueness Controversy.

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.

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 .  |  . 214 .  |  .  .  .
. 423 .  |  . 32  .  |  .  .  .
.  31 .  |  . 13  .  |  .  .  .

Without the additional candidates, the pattern would be deadly. Thus, at least one of the additional candidates must be correct. In this particular example, we may eliminate candidate 4 from all cells that can see both blue candidates.

Deadly patterns and minimal unavoidable sets

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