The New Sudoku Players' Forum

[nazaz]

Example

Here's an interesting example of a pattern (of pencilmarks) on five cells that's "deadly" in the sense that, without an extra candidate, every solution is unavoidable (contains a minimal unavoidable set):


Code: Select all

23 .  1  | 23 .  .
.  .  .  | .  .  .
.  .  23 | 1  .  .

No matter how r1c1 is set, you get a U4 on the other cells.

Definition

You could call this a generalised deadly pattern (GDP):

1. It's a union of unavoidables. (No requirement that they be minimal UAs.)
   
2. As a puzzle in its own right, each of its solutions is unavoidable. (It's an unavoidable union of unavoidables! -- a UUU.)
3. It's not enriched by any other UUU. (A cosmetic choice that the pattern should be "maximal".)
Here, to "enrich" a pattern is to add further pencilmarks to a cell or to remove a cell from consideration. The converse is "depletion". Any pattern of pencilmarks that is a depletion of a GDP either has no solutions or has only unavoidable solutions, so at least one other candidate must be true.

PS: like point iii, point ii above is also a cosmetic choice: it ensures that the pattern doesn't include impossible candidates.

Another example

It's easy to find many examples of GDPs not covered by Sudopedia's DP definition. To finish, here's one more example:


Code: Select all

    1    23  .  |  4
    234  .   .  |  1
    ------------+---
    23   1   .  |  .

[denis_berthier]

Example

Here's an interesting example of a pattern (of pencilmarks) on five cells that's "deadly" in the sense that, without an extra candidate, every solution is unavoidable (contains a minimal unavoidable set):


Code: Select all

23 .  1  | 23 .  .
.  .  .  | .  .  .
.  .  23 | 1  .  .

No matter how r1c1 is set, you get a U4 on the other cells.

I don't understand a single bit of what you're saying.
First, are you talking of deadly patterns (DPs) or of unavoidable sets (UAs)?

Second, if I set r1c1 = 2, what I get is:

Code: Select all

2  .  1  | 3  .  .
.  .  .  | .  .  .
.  .  3  | 1  .  .

Where is the U4?
.

[eleven]

Nazaz,

you did not mention, that the singles in your patterns must not be givens of a puzzle, otherwise the patterns are not deadly, but useless.
Without givens, i doubt, that your patterns will appear in the solving process of a puzzle, at least not without being part of a known MUG in an earlier state.
So you should provide us with a real world example.

[nazaz]

Yes, that's right, unclued cells (... "a pattern (of pencilmarks)" ...).

I don't know if the particular patterns shown in either example would appear in a solution path. It would be interesting to find out, though usefulness to solvers is not my priority.

I made a point of picking those 5-cell and 7-cell examples only to demonstrate how GDPs can include patterns not previously considered to be "deadly". Since dobrichev challenged us to consider the possibility of 7-cell DPs, I've been of the opinion that Sudopedia's DP definition is too narrow and needs generalising. The three criteria that I've listed in the opening post (to paraphrase: that a GDP is a maximal unavoidable union of unavoidables) seem to be a good way of performing that generalisation.
There's a small bug in the "PS", though: it's point i, not ii, that ensures that there are no impossible candidates.

The definition is attractive for a few reasons. It's very simple. It has a good notion of maximality (via enrichment). It invites exploration of the natural question: what happens to "unavoidability" when I mash several UAs together? It includes DPs based on strongly-minimal UAs (per Sudopedia). It includes patterns that are enrichments of dobrichev's example. Maybe it includes MUGs; I don't know if they were ever defined rigorously.

[eleven]

Basically a MUG is any candidates pattern (without singles) with at least 2 solutions, which in all possible solution grids leave an unavoidable set in the MUG cells.
In other words, whatever numbers you place outside, they would leave 0 or at least 2 pattern solutions.
A pattern can be proved to be a MUG by calculating all solutions and their footprints. If no footprint is unique, it is a MUG.
Since from this definition every candidates grid of a multi solution puzzle is a MUG, we are only interested in smaller MUG's, e.g. by eliminating cells, which do not affect the MUG property.
(As an example: in the "puzzle" without any givens you could eliminate all but 2 rows in a band)

[nazaz]

If no footprint is unique, it is a MUG.

That's a sufficient condition for the MUG definition in your first sentence, but is not necessary.

Consider, for example

Code: Select all

    ... ... 1.3 | ... ... ... | 123
    ... ... 123 | .23 ... ... | 1.3
    ... ... .23 | 123 ... ... | ...

in which the solution

Code: Select all

    ... ... 1.. | ... ... ... | .2.
    ... ... .2. | ..3 ... ... | 1..
    ... ... ..3 | 1.. ... ... | ...

has a unique footprint.

The test aside, it seems GDPs and MUGs might be pretty much the same thing except for cosmetic choices (maximal enrichment & no impossible candidates in GDPs; no singles in MUGs). Both are useful generalisations of Sudopedia's overly-narrow DP definition. It's a pity that MUGs don't have their own article on Sudopedia.

[eleven]

Yes, that pattern is not a MUG, because this footprint is unique.

[nazaz]

Would you say it was "deadly" though?

By my definition of a GDP, it is. Each of its solutions is an unavoidable.

[eleven]

I don't understand you, this pattern is neither deadly nor a MUG.
Place a 2 in r4c4 and a 3 in r7c7 and you get this single pattern solution.

[nazaz]

That "single pattern solution" is an unavoidable, though! By uniqueness, it can't be present in the solution grid.

Let's discuss a smaller example. The following is a GDP plus an extra candidate (the 9). By uniqueness, the extra candidate must be true; I hope you agree.

Code: Select all

23 .  19 | 23 .  .
.  .  .  | .  .  .
.  .  23 | 1  .  .

(The isolated 1 is a naked single, not a given.)

This example doesn't pass your duplicate-footprint or no-naked-singles requirements for a MUG. So this is a situation where GDPs can help, but MUGs can't. Is there a good reason to limit the scope of MUGs in this way?

[eleven]

That "single pattern solution" is an unavoidable, though! By uniqueness, it can't be present in the solution grid.

No, to my knowledge there is no unavoidable set of size 7 at all [edit: (thanx to nazaz) this is only true for minimal unavoidables, however this one is not unavoidable]

Let's discuss a smaller example. The following is a GDP plus an extra candidate (the 9). By uniqueness, the extra candidate must be true; I hope you agree.

Code: Select all

23 .  19 | 23 .  .
.  .  .  | .  .  .
.  .  23 | 1  .  .

(The isolated 1 is a naked single, not a given.)

This example doesn't pass your duplicate-footprint or no-naked-singles requirements for a MUG. So this is a situation where GDPs can help, but MUGs can't. Is there a good reason to limit the scope of MUGs in this way?

I agree, this pattern is both deadly and no MUG. The trick is, that it can end in 2 different solution grids with an unavoidable set. Would be nice to see a real world example.

[Added:] btw with the resolved 1r3c4 you don't even need the uniqueness assumption to place the 9r1c3 (because you already know, that r1c4/r2c3 can't be 1 to allow a second solution).

[eleven]

Hm, sorry for being blind for the 12 U4 in the 7 cell GDP above, which makes this unique footprint unavoidable.
So we have the same property, that in all possible (and different) solution grids for that pattern there will occur an unavoidable set.

[nazaz]

So it looks like GDPs & their depletions include but are not limited to MUGs. Cool

There's potentially a whole zoo of GDPs similar in style to the GDP-5 shown in the first post. Start with empty cells A,B,C,D (labelled clockwise) in a "U4"-style configuration. Place candidates in those and any other cells in a way that forces A=C and B=D. The result is deadly. Once pruned of impossible candidates and fully enriched, it's a GDP.

[StrmCkr]

this reads more like an extension to the UR1.1 theory then anything new.

by expanding it outwards for +1 cell AND Linking it directly to both the cells in its visible range guarantee the outcome doesn't change.

http://forum.enjoysudoku.com/post287631.html#p287631

Theorem: if a puzzle-in-progress (that does not necessarily have a unique solution) has pencil-marks as shown below on four unclued cells then the bottom right value resolves to '3':

Code: Select all

     .  .  . | .
     1  .  . | 2
     2  .  . | 13
    ---------+---
     .  .  . | .

what i said above as a picture.

Code: Select all

     .  .  . | .   . 
     1  .  . | 23   .   
     23 .  . | 13  23
    ---------+---
     .  .  . | .

this pattern never exists in the wild as he 23 naked pair would always resolve r3c3 as 1. { not three like the above}
which means two of the three "23" cells cannot be a naked pair, other wise it is always in a muti-solution state.

[nazaz]

this reads more like an extension to the UR1.1 theory

Good, that's another example of a pattern covered by GDPs. Maybe the extension (the "zoo") is new, maybe not.

The definition of GDPs given in the first post says nothing about what they look like in practice, so it's helpful to confirm that well-known families of "deadly patterns" are covered by that definition.