The New Sudoku Players' Forum

[denis_berthier]

such that P has several different solution grids

If your aim is to use DPs to solve valid puzzles, they only have one solution grid.

I explicity stated that P may be multi-sol.

[denis_berthier]

what does the term "resolution state" mean? (In Sudoku puzzles solving context)
I don't understand your comment "which is ensured by the fact that RS is a resolution state of P". What do you mean?

When solving a puzzle in the usual ways, we go through a sequence of RSs. This expression, introduced in my first book [HLS, 2007] is now used by almost everybody.
To make it simple, a RS of a (possibly multi-solution) puzzle P is any set of candidates that is compatible with the givens (in a cell with a given, you can't have other candidates). The smallest possible RS is the set of candidates common to all the solutions of P. The largest possible RS for P is the set with all the digits in all the cells with no given.
For a cleaner definition, see [PBCS].

As for the "ensured" part, if you have reached some RS for P (by consistent methods), any solution for P can only be consistent with RS.
.

[marek stefanik]

I'll try it again.

Code: Select all

 +--------------------+-----------------------+-------------------------+
 |  12*   12*    3    |  4      5      6      |  7        8      9      |
 |  45    45     7    |  1      8      9      |  26       3      26     |
 |  6     9      8    |  3      2      7      |  145      145    45     |
 +--------------------+-----------------------+-------------------------+
 |  12*   12+8*  45   |  69     369    18     |  36       45     7      |
 |  458   3      6    |  2      7      458    |  458      9      1      |
 |  7     1458   9    |  568    1346   1458   |  34568    2      4568   |
 +--------------------+-----------------------+-------------------------+
 |  3     6      45   |  5789   149    1458   |  124589   1457   2458   |
 |  458   7      2    |  589    149    3      |  14589    6      458    |
 |  9     458    1    |  5678   46     2      |  458      457    3      |
 +--------------------+-----------------------+-------------------------+

2. UR(12)r14c12, using single internal => +8 r4c2; lcls, 7 placements

By your definition, this is not a DP as the puzzle has only one solution grid (which doesn't even contain a corresponding unavoidable set).

Marek

[denis_berthier]

By your definition, this is not a DP as the puzzle has only one solution grid (which doesn't even contain a corresponding unavoidable set).

Exact. This is not a DP. It's a DP + a guardian.

[marek stefanik]

So you agree that 12r14c12 is a DP in that RS.

Code: Select all

A deadly pattern (DP) in some resolution state RS of a consistent but possibly multi-solution Sudoku puzzle P is a pair (S, C) of sets – a set S of cells and the set C of their sets of candidates in RS – such that P has several different solution grids:
–   which coincide outside S but differ pairwise by all their values in S;
–   and compatible with (S, C), i.e. for which the value in any cell of S belongs to the corresponding set of candidates in C (which is ensured by the fact that RS is a resolution state of P).

But your definition requires P to have multiple solution grids, which is not the case.

Marek

[denis_berthier]

This is not a DP.

What is the word you don't understand in this sentence?

[marek stefanik]

You said it is a DP + a guardian, yet no part of it would be considered a DP by your definition.

[denis_berthier]

.
We have the same abuse of language for impossible patterns.
.

[denis_berthier]

.
Here's my updated version of the definition + how to use a DP.

Code: Select all

Definition: a deadly pattern (DP) in some resolution state RS of a consistent but possibly multi-solution Sudoku puzzle P is a pair (S, C) of sets – a set S of cells and the set C of all their (nrc) candidates in RS – such that:
–--   P has several different solution grids which coincide outside S but differ pairwise by at least one value in a cell of S;
–--   any element of C appears in at least one of the solutions.

Note that, because RS is a resolution state of P, any solution can only be compatible with (S, C), i.e. for any solution the value of any cell in S belongs to the corresponding set of candidates in C.

Definition: a deadly pattern (S, C) is minimal if there is no strictly smaller deadly pattern, i.e. with smaller S or with fewer candidates in C.

Definition: a deadly pattern (S, C) is minimal if there is no strictly smaller deadly pattern, i.e. with smaller S or with fewer candidates in C.

As no deadly pattern can ever appear in a single-solution puzzle, DPs can have a direct application in solving puzzles (provided that one accepts the assumption of uniqueness): when one finds something close to a DP, i.e. a DP with additional candidates (guardians), one can assert a disjunction of the guardians (an OR relation between the guardians). From there, everything can work as with impossible patterns.

.

[eleven]

My definition is:

A deadly (uniqueness) pattern is a pattern with at least 2 internal solutions, which cannot be made unique by placing digits outside.
(To prove a bigger pattern deadly can be very complex and normally needs to calculate all solutions and footprints).

An exception is a BUG, which has no solution.

Also (more generally) in cells without givens a pattern of single digits is deadly, if it corresponds to an unavoidable set.

Furthermore there are special deadly patterns like reverse BUGs.

[marek stefanik]

The definition on sudopedia is imo a good definition of a type of DPs, non-permeable DPs without internal contradictions with only cell truths.
Denis' definition is allegedly an attempt at defining the same concept, but in reality, it is vastly different.
Eleven's definition is a nice way to cover most (if not all) DPs without internal contradictions.
That is also it's weakness, in some sense, as because of this generality, it cannot tell you anything about what DPs actually look like.

By sudopedia's definition, 12r14c12 is a DP (which cannot appear in a unique puzzle without guardians).
Denis, your definition is based on a fixed RS and all candidates of the cells.
There cannot be 'something close to a DP, i.e. a DP with additional candidates (guardians)', as you write, because then the DP (without the guardians) would only contain a subset of the cells' candidates and would not be a DP by your definition.

Consider this puzzle:
...3467896..789125789125346..64375988..951267957268413361872954498513672572694831
The resolution state at the start is the following, where 05 in r1c3 means that 5 is the only candidate, but is not filled in.

Code: Select all

,------------,---------,---------,
| 12  12  05 | 3  4  6 | 7  8  9 |
| 6   34  34 | 7  8  9 | 1  2  5 |
| 7   8   9  | 1  2  5 | 3  4  6 |
:------------+---------+---------:
| 12  12  6  | 4  3  7 | 5  9  8 |
| 8   34  34 | 9  5  1 | 2  6  7 |
| 9   5   7  | 2  6  8 | 4  1  3 |
:------------+---------+---------:
| 3   6   1  | 8  7  2 | 9  5  4 |
| 4   9   8  | 5  1  3 | 6  7  2 |
| 5   7   2  | 6  9  4 | 8  3  1 |
'------------'---------'---------'

What DPs (according to your definition) can we identify?
Not 12r14c12, as not all solutions coincide outside it. Not 34r25c23 for the same reason.
We can, however, identify the DP 12r14c12 34r25c23, which is thus the only minimal DP.
12r14c12 34r25c23 5r1c3 also meets your requirements for a non-minimal DP.
As such, your definition is closer to a definition of true candidates (but it leaves the candidates of decidable cells as optional) than of DPs.

In comparison, by sudopedia's definition, the URs are the two minimal DPs and their union is a non-minimal DP.
If we add in 5r1c3 (to any of the 3), it will no longer be a DP by sudopedia's definition.

Marek

[eleven]

Eleven's definition is a nice way to cover most (if not all) DPs without internal contradictions.
That is also it's weakness, in some sense, as because of this generality, it cannot tell you anything about what DPs actually look like.

The sudopedia definition tells you more, how DPs actually look like ?
[Added:] Maybe you mean the lack of minimality. I could add something like: Cells, which don't affect this property, can be excluded.

As i already had mentioned, deadly patterns should not be restricted to 2 candidates per cell. It's an misleading name then, because MUGs follow exactly the same concept.

[Edit: deleted unneccessary question]

[nazaz]

Definition: a deadly pattern (S, C) is minimal if there is no strictly smaller deadly pattern, i.e. with smaller S or with fewer candidates in C.

Should be: with more candidates in C. The givens in a DP are its non-candidates, i.e. the complement of the pencilmarks.

[marek stefanik]

'DPs without internal contradictions' is a term I use to explicitly exclude BUGs and similar patterns with no solutions.

This is the sudopedia definition:

Code: Select all

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

It is not restricted to patterns of bivalue cells.

I believe it is a bit more descriptive than any general definition could be.
I don't mean minimality, I mean that it tells the solver to look for cells satisfying some (arguably still somewhat abstract) criteria.
A general definition like the one you gave cannot do that.
Your definition covers permeable DPs.
Your definition covers reverse BUG, i.e. a situation where two digits are not fully filled and their unfilled instances are restricted to the same cells. Here 'placing digits outside' would mean placing other digits.

As a side note, MUG is also a misleading term.
It is derived from BUG, bivalue universal grave, where the 'universal' means that is spans every unresolved cell.
Though, that is not the case for the patterns which we usually refer to as MUGs.

Marek

[eleven]

You are right, the definition speaks of multiple solutions, but in the following they restrict to minimal unavoidable sets and bivalue cells.
My definition comes from manually proving/disproving deadly patterns. e.g. in the sudopedia sample

Code: Select all

.  12 .  |  . 213 .  |  .  .  .
. 123 .  |  . 32  .  |  3 .  .
.  31 .  |  . 13  .  |  .  .  .


just set 3 in r2c7 to get a single pattern solution.