Rooted: Created page with "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 encounter..."

2020-05-31T20:05:33Z

Created page with "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 encounter..."

New page

A '''deadly pattern''' is a set of [[cell]]s whose [[candidate]]s form a pattern that causes the puzzle to have multiple [[solution]]s. 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 Test|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 . | . 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 [[Mathematically equivalent|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 Test|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 ==

* [http://www.sudoku.com/forums/viewtopic.php?t=3056 BUG Lite thread] on the Sudoku Players' forum
* [http://www.sudoku.com/forums/viewtopic.php?t=2747 Pseudo-puzzles thread] on the Sudoku Players' forum

== See also ==

* [[Unique Rectangle]]
* [[BUG]]
* [[BUG Lite]]
* [[Uniqueness Test]]

{{debate}}

[[Category:Uniqueness]]

Deadly Pattern - Revision history

Rooted: Created page with "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 encounter..."