Unique Solution Premise
A valid Sudoku puzzle has a unique solution. Uniqueness-based solving techniques should only be used on valid Sudoku puzzles. *)
From the POV of the puzzle setter: In a valid Sudoku puzzle each unavoidable set is covered by at least one given value.
From the POV of the player: A valid Sudoku puzzle either has been validated (by some software) or comes from a trusted source. The latter is not 100% proof, so in this case we speak of Uniqueness Assumption.
Uniqueness-based solving techniques can never be used to prove that a Sudoku puzzle is valid.
*) (pseudo-)Puzzles with multiple solutions will contain deadly patterns with no escape (DP+0). Avoiding such a pattern using uniqueness-based techniques will reduce the number of solutions by a factor equal to the number of solutions to this pattern. In the end you with either find 0 or 1 solution.
Unavoidable Sets
Unavoidable sets exist in a solution grid. An unavoidable set is a group of cells which can be changed in such a way that another valid solution can be formed by only altering the cells inside this set.
The smallest unavoidable set has 4 cells. The largest unavoidable set has 81 cells. Any two rows or columns in a single chute form an unavoidable set of 18 cells. The combined cells for any pair of numbers also form an unavoidable set of 18 cells.
An unavoidable set can be a subset of one or more larger unavoidable sets. For example: A bivalue rectangle located in a single chute is both a subset of the unavoidable set for the 2 lines in that chute and of the unavoidable set for all 18 cells holding these two numbers.
Observation: Each unavoidable set has a complementary unavoidable set in each of its parents. This complementary set contains all the remaining cells in this parent.
Unavoidable sets can also intersect with other unavoidable sets. The union of these sets can be seen as unavoidable sets by themselves, but their constituent sets are not true subsets, since their complements are not unavoidable sets.
As stated above, in a valid Sudoku puzzle each unavoidable set is covered with at least one given value. As a result, a valid Sudoku puzzle does not contain unavoidable sets in which none of the cells contains a given value.
Deadly Patterns
An deadly pattern is a set of candidates which is a subset of the combined candidate space of an unavoidable set and all its alternative solutions, which contains no given numbers. The pattern may contain solved cells, but the solved values must belong to the same candidate space.
A little lateral thinking is required here. We know that a valid Sudoku does not contain unavoidable sets without given values, so how can we find any of them in the PM grid? The answer is best illustrated with an example:
- Code: Select all
+-----------------------+
| 1 . . | 2 . . | . . . |
| 2 . . | 1 . . | . . . |
| . . . | . . . | . . . |
|-------+-------+-------|
The cells r12c14 form an unavoidable set.
The alternative solution to these 4 cells is also an unavoidable set:
- Code: Select all
+-----------------------+
| 2 . . | 1 . . | . . . |
| 1 . . | 2 . . | . . . |
| . . . | . . . | . . . |
|-------+-------+-------|
The combined candidate space is this set. If none of these 4 cells contains a given number, any subset of this set qualifies as a deadly pattern:
- Code: Select all
+--------------------------------+
| 12 . . | 12 . . | . . . |
| 12 . . | 12 . . | . . . |
| . . . | . . . | . . . |
|----------+----------+----------|
Here is the candidate space for two intersecting bivalue rectangles:
- Code: Select all
+--------------------------------+
| 12 . . | 12 . . | . . . |
| 12 . . | 123. . | 13 . . |
| . . . | 13 . . | 13 . . |
|----------+----------+----------|
It has 3 solutions (each of them is an unavoidable set):
- Code: Select all
+-----------------------+
| 1 . . | 2 . . | . . . |
| 2 . . | 1 . . | 3 . . |
| . . . | 3 . . | 1 . . |
|-------+-------+-------|
+-----------------------+
| 2 . . | 1 . . | . . . |
| 1 . . | 2 . . | 3 . . |
| . . . | 3 . . | 1 . . |
|-------+-------+-------|
+-----------------------+
| 1 . . | 2 . . | . . . |
| 2 . . | 3 . . | 1 . . |
| . . . | 1 . . | 3 . . |
|-------+-------+-------|
This pattern is also covered by this trivalue set, but it is not a true subset, since the remaining cells do not form a complementary set.
- Code: Select all
+-----------------------------------+
| 123 . . | 123 . . | 123 . . |
| 123 . . | 123 . . | 123 . . |
| 123 . . | 123 . . | 123 . . |
|-----------+-----------+-----------|
In a valid Sudoku, there must be at least one additional candidate in the cells belonging to a deadly pattern. Additional candidates are known as surplus candidates. Also, there must be at least one additional candidate in 3 of the unit constraints covered by the pattern. Together, these are the 4 escapes that must accompany the deadly pattern.
An example:
- Code: Select all
+--------------------------------+
| 12 . . | 12 . . | . . . |
| 12 . . | 12 . . | . . . |
| . . . | . . . | . . . |
|----------+----------+----------|
To escape this deadly pattern:
- at least one of the cells must have a candidate for a number other than 1 or 2;
- at least one of the rows 1 & 2 must have a candidate 1 or 2 not in columns 1 and 4;
- at least one of the boxes must have a candidate for number 1 or 2 outside these 4 cells;
- at least one of the columns must also have an additional candidate for number 1 or 2.
Each of these 4 conditions can be used in the definition of uniqueness-based solving techniques.
Bivalue vs. Multivalue deadly patterns
An deadly pattern is a bivalue pattern when all the cells have exactly 2 candidates. All other deadly patterns are multivalue patterns. For specific cases, we can use terms like trivalue. These names are useful to identify multivalue patterns which appear more frequent and are easy to recognize.
Complete vs. Partial deadly patterns
A complete deadly pattern contains all unsolved cells in the grid. A BUG is an example of a complete (bivalue) deadly pattern. An partial deadly pattern only contains a part of the unsolved cells. UR and BUG-Lite are examples of partial deadly patterns.
Avoiding Deadly Patterns
Any (combination of) move(s) which would result in a deadly pattern which does not have all 4 escapes is an invalid (combination of) move(s). Blocking a single escape is sufficient to enforce the deadly pattern. Therefore, for any set of surplus candidates in each the 4 constraint sets we can deduce:
- If there is a single surplus candidate, it can be placed.
- If all candidates belong to a single cell or unit constraint, the candidates in the intersection of this constraint and the deadly pattern can be eliminated.
- If there are two surplus candidates, they are strongly linked.
- If there are two groups of candidates in 2 constraints, these groups are strongly linked.
It is also possible to establish a link between escapes in different constraint types.
I'm using the following symbols:
- Code: Select all
* : One or more candidates belonging to the deadly pattern
/ : One or more candidates not found in the deadly pattern
. : anything (given, solved, any group of candidates)
A,B,C : A candidate that provides an escape in a row, column or box
x,y,z : A candidate that provides an escape in a cell belonging to the deadly pattern
- Code: Select all
+--------------------------------+
| */ / / | */ / / | A/ / / |
| *x . . | * . . | . . . |
| . . . | . . . | . . . |
|----------+----------+----------|
In this example, A is the only surplus candidate in row 1. x is the only surplus candidate in the 2 cells that belong to row 2. Either r1c6=A or r2c1=x.
Lexicon of known Deadly Patterns
I will complete this section later. It will contain a canonicalized representative of each type of pattern.
- Code: Select all
Unique Rectangle (UR): 4 cells, bivalue, partial
+-----------------------------------------+
| 12 12 . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
|-------------+-------------+-------------|
| 12 12 . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
|-------------+-------------+-------------|
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-----------------------------------------+
Lexicon of known Escape Routes
Another section to be completed. When the previous material has passed the scrutiny of the experts, we can start a list of known solving techniques which can be seen as escape routes from a deadly pattern.
References
- Unique Rectangles http://forum.enjoysudoku.com/viewtopic.php?p=29105#p29105
- - Types 1-4 http://www.setbb.com/phpbb/viewtopic.php?p=2441
- - More types 1-4 http://forum.enjoysudoku.com/viewtopic.php?t=2000
- - Diagonal and X-wing types http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?p=2894#p2894
- - Strong Link and Nice Loop Types http://forum.enjoysudoku.com/viewtopic.php?p=26448#p26448
- - ALS Types http://forum.enjoysudoku.com/viewtopic.php?p=28313#p28313
- - With Missing Candidates http://forum.enjoysudoku.com/viewtopic.php?t=3967
- - Almost Unique Rectangles (AUR) http://forum.enjoysudoku.com/viewtopic.php?t=2751
- Unique Loops http://forum.enjoysudoku.com/viewtopic.php?p=39748#p39748
- - Almost Unique Loops http://forum.enjoysudoku.com/viewtopic.php?t=2751
- Bivalue Universal Grave (BUG) http://forum.enjoysudoku.com/viewtopic.php?t=2352
- - Reverse BUG http://forum.enjoysudoku.com/viewtopic.php?t=4431
- BUG Lite http://forum.enjoysudoku.com/viewtopic.php?t=3056
- - Strong Link Types http://forum.enjoysudoku.com/viewtopic.php?p=27034#p27034
- - Advanced Types http://forum.enjoysudoku.com/viewtopic.php?p=30741#p30741
- - Reverse BUG Lite http://forum.enjoysudoku.com/viewtopic.php?t=4957
- Deadly Intertwined Patterns http://forum.enjoysudoku.com/viewtopic.php?t=5594
- Almost Unavoidable Set (AUS) http://forum.enjoysudoku.com/viewtopic.php?p=22180#p22180