(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

## 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

```. 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.

## 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 .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
.  .  .  |  .  .  .  |  .  .  .
```