The New Sudoku Players' Forum

by **blue** » Sat Jan 11, 2025 9:33 pm

Below, is the list of deadly patterns that can be produced from the (strongly) minimal UA sets with size <= 12 -- 2 characters per cell.
(For size <= 12, the minimal UA sets ... 525 of them ... are all "strongly minimal", with valency=2).

There are only 408 "essentially distinct" deadly patterns.
These are the minlex forms.

For the ones with "(size,1)" at the end of the line, the two solutions are isomorhpic ... they have the same minlex form.
For the "(size,2)" cases, that isn't the case. Each of those, accounts for two (essentially) distinct UA sets.
There are 291 "(size,1)", and 117 "(size,2)" cases ... 291 + 2 * 117 = 525.

Hidden Text: Show

Website · by **denis_berthier** » Sun Jan 12, 2025 8:49 am

Hi Blue
Thanks for the list. It's exactly what I needed.
I'm busy today, but I'll work on it tomorrow.
.

by **eleven** » Sun Jan 12, 2025 6:26 pm

For a (manual) solver MUG's are more interesting, because they are not that rare / have less extra candidates as some multi-cell DP's with 2 candidates.
E.g. you can look for this MUG

Code: Select all: 123 123 123 . . . . . . ------------ 123 123 123 . . . . . .

instead of that DP

Code: Select all: 12 23 13 . . . . . . ------------ 13 12 13 . . . . . .

or this one

Code: Select all: . . . | . . . . . . | . . . . . . | . 12 12 -------------------- . . 134 | . . 134 . . 134 | . 134 . . . 234 | . 234 234

instead of that

Code: Select all: . . . | . . . . . . | . . . . . . | . 12 12 -------------------- . . 13 | . . 13 . . 14 | . 14 . . . 34 | . 24 23

Website · by **denis_berthier** » Mon Jan 13, 2025 3:48 am

blue wrote:For the ones with "(size,1)" at the end of the line, the two solutions are isomorhpic ... they have the same minlex form.
For the "(size,2)" cases, that isn't the case. Each of those, accounts for two (essentially) distinct UA sets.

Is this distinction related to the type of permutation inside the UA?

About guardians. I think we can use the same name as in impossible patterns: in one case they guard against contradiction, here they guard against non-uniqueness.
As I understand the notation, in a pattern such as ... . . . 12 23 34 . . . ...
- any digit other than 1 and 2 in cell "12" is a guardian
- any digit other than 2 and 3 in cell "23" is a guardian
...

I've finally had time yesterday evening to adapt your list to the format I used in the rule generators I've written a few days ago.
I takes SudoRules 3s on my Mac to generate the 4x408 ORk-detection rules derivable from it.
The factor 4 is decomposed as:
- 2 for row-column symmetry. as those are not generic rules, I need to explicitly use rows, columns, blocks... and therefore
- 2 for activation + detection

First decision was to choose a cutoff for the number of guardians allowed. I chose 8.
I tried a first run with all the rules loaded but it quickly led to very long computation time and to memory saturation for some puzzles (even with 64 GB).
Therefore, I restricted my computations to DPs with 11 or fewer cells. Computations are still slow, but they are manageable.
After running during the night, it appears that:
- many DPs must exist with more than 8 guardians
- very few DPs with ≤ 8 guardians and ≥ 8 cells exist
- based on the 1st 8,000 puzzles in cbg-000, there not a single example where the W + DP9-O6W and W + DP11-ORW would be different

I've found only one instance of a DP11 (but it's useless in the puzzle):

Code: Select all: Puzzle cbg-000 #5600 +-------+-------+-------+ ! . 2 . ! 4 5 . ! . . . ! ! . 5 . ! 1 . 9 ! 2 . . ! ! 6 8 . ! . . . ! 1 . 4 ! +-------+-------+-------+ ! 2 . . ! 7 . 8 ! . . . ! ! 7 . 6 ! . 4 5 ! . . . ! ! . . . ! . 9 . ! . . . ! +-------+-------+-------+ ! . . . ! . 7 . ! 9 . . ! ! 5 . 4 ! . . . ! . 6 . ! ! . . . ! 5 . 3 ! . . . ! +-------+-------+-------+ .2.45.....5.1.92..68....1.42..7.8...7.6.45.......9........7.9..5.4....6....5.3... 98622

Code: Select all: Resolution state after Singles and whips[1]: +-------------------+-------------------+-------------------+ ! 13 2 137 ! 4 5 6 ! 378 3789 3789 ! ! 4 5 37 ! 1 8 9 ! 2 37 6 ! ! 6 8 9 ! 23 23 7 ! 1 5 4 ! +-------------------+-------------------+-------------------+ ! 2 1349 5 ! 7 13 8 ! 6 1349 139 ! ! 7 139 6 ! 23 4 5 ! 38 12389 12389 ! ! 8 134 13 ! 6 9 12 ! 5 12347 1237 ! +-------------------+-------------------+-------------------+ ! 13 6 2 ! 8 7 4 ! 9 13 5 ! ! 5 37 4 ! 9 12 12 ! 378 6 378 ! ! 9 17 8 ! 5 6 3 ! 4 127 127 ! +-------------------+-------------------+-------------------+ 94 candidates.

Code: Select all: DP4-2-1s-OR7-relation in cells (marked #): (r9c9 r9c8 r6c9 r6c8) with 7 guardians (in cells marked @) : n7r9c9 n7r9c8 n3r6c9 n7r6c9 n3r6c8 n4r6c8 n7r6c8 +-------------------------+-------------------------+-------------------------+ ! 13 2 137 ! 4 5 6 ! 378 3789 3789 ! ! 4 5 37 ! 1 8 9 ! 2 37 6 ! ! 6 8 9 ! 23 23 7 ! 1 5 4 ! +-------------------------+-------------------------+-------------------------+ ! 2 1349 5 ! 7 13 8 ! 6 1349 139 ! ! 7 139 6 ! 23 4 5 ! 38 12389 12389 ! ! 8 134 13 ! 6 9 12 ! 5 12347#@ 1237#@ ! +-------------------------+-------------------------+-------------------------+ ! 13 6 2 ! 8 7 4 ! 9 13 5 ! ! 5 37 4 ! 9 12 12 ! 378 6 378 ! ! 9 17 8 ! 5 6 3 ! 4 127#@ 127#@ ! +-------------------------+-------------------------+-------------------------+

Code: Select all: DP4-2-1s-OR8-relation in cells (marked #): (r9c9 r9c8 r5c9 r5c8) with 8 guardians (in cells marked @) : n7r9c9 n7r9c8 n3r5c9 n8r5c9 n9r5c9 n3r5c8 n8r5c8 n9r5c8 +-------------------------+-------------------------+-------------------------+ ! 13 2 137 ! 4 5 6 ! 378 3789 3789 ! ! 4 5 37 ! 1 8 9 ! 2 37 6 ! ! 6 8 9 ! 23 23 7 ! 1 5 4 ! +-------------------------+-------------------------+-------------------------+ ! 2 1349 5 ! 7 13 8 ! 6 1349 139 ! ! 7 139 6 ! 23 4 5 ! 38 12389#@ 12389#@ ! ! 8 134 13 ! 6 9 12 ! 5 12347 1237 ! +-------------------------+-------------------------+-------------------------+ ! 13 6 2 ! 8 7 4 ! 9 13 5 ! ! 5 37 4 ! 9 12 12 ! 378 6 378 ! ! 9 17 8 ! 5 6 3 ! 4 127#@ 127#@ ! +-------------------------+-------------------------+-------------------------+

Code: Select all: DP11-3-31s-OR8-relation in cells (marked #): (r3c4 r3c5 r8c6 r8c5 r4c2 r4c5 r6c9 r6c6 r5c9 r5c2 r5c4) with 8 guardians (in cells marked @) : n4r4c2 n9r4c2 n3r6c9 n7r6c9 n3r5c9 n8r5c9 n9r5c9 n9r5c2 +-------------------------+-------------------------+-------------------------+ ! 13 2 137 ! 4 5 6 ! 378 3789 3789 ! ! 4 5 37 ! 1 8 9 ! 2 37 6 ! ! 6 8 9 ! 23# 23# 7 ! 1 5 4 ! +-------------------------+-------------------------+-------------------------+ ! 2 1349#@ 5 ! 7 13# 8 ! 6 1349 139 ! ! 7 139#@ 6 ! 23# 4 5 ! 38 12389 12389#@ ! ! 8 134 13 ! 6 9 12# ! 5 12347 1237#@ ! +-------------------------+-------------------------+-------------------------+ ! 13 6 2 ! 8 7 4 ! 9 13 5 ! ! 5 37 4 ! 9 12# 12# ! 378 6 378 ! ! 9 17 8 ! 5 6 3 ! 4 127 127 ! +-------------------------+-------------------------+-------------------------+

solution in W2

Website · by **denis_berthier** » Mon Jan 13, 2025 3:51 am

eleven wrote:For a (manual) solver MUG's are more interesting, because they are not that rare / have less extra candidates as some multi-cell DP's with 2 candidates.
E.g. you can look for this MUG
Code: Select all
123 123 123 . . . . . . ------------ 123 123 123 . . . . . .

instead of that DP
Code: Select all
12 23 13 . . . . . . ------------ 13 12 13 . . . . . .

OK, but if you define the pattern as in the above MUG, how do you know what the guardians are?
Or do you mean that you look only for DPs whose guardians are the candidates in the MUG but not in the DP?

[Edit]: on second thoughts, I think defining a MUG as a DP that has only guardians from the digits in the DP would make an alternative way of restricting the number of guardians in DP. I don't know if this is (or is equivalent to) the standard definition of a MUG (if such a thing exists).
For me, it would require to write a slightly different version of my DP detection rules, but it'd be easy to do.
However, I doubt that the final results about the resolution power would be much more positive.
.

by **eleven** » Mon Jan 13, 2025 1:45 pm

MUG's are deadly uniqueness patterns, complete or not. The bigger they are, the more rare they seem to be. In hard puzzles very seldom a DP is really useful because of the many extra candidates (maybe with the exception of tridagon puzzles with their special structure), but sometimes they can be integrated in chains.
This simple pattern has been used several times in the puzzle thread, in what you would call easy puzzles.
For the other one i posted i could not find a good application so far, just this one to get an "elegant" solution in an (also manual) easy puzzle:

Hidden Text: Show

Website · by **denis_berthier** » Mon Jan 13, 2025 3:15 pm

.
There's a delicate balance to find between the time when we look for deadly or impossible patterns and the number of guardians we allow:
- too early and there are too many cases, with too many guardians;
- too late and the pattern disappears or at least becomes degenerate and harder to find.
And it's seems the balance is different between the impossible and the deadly cases (deadly ones are more easily destroyed and require still earlier detection).

By combining early detection with ultra-persistency + splitting rules for the ORk-relations, I think I've solved part of this balance problem, but with this early detection there remains cases with too many patterns at the start (that are finally useless).
In the cbg-000 collection, DP4's are very frequent, but most often useless. Larger DPs are rare (extremely rare for > 6 cells).
Maybe harder puzzles would give better results.

I've tried your puzzle with Blue's 408 DPs on ≤ 12 cells activated, with at most 98 guardians, but it doesn't give anything. Three DP4s appear, but are useless.

Code: Select all: DP4-2-1s-OR7-relation in cells (marked #): (r9c9 r9c8 r6c9 r6c8) with 7 guardians (in cells marked @) : n3r9c9 n4r9c9 n3r9c8 n4r9c8 n3r6c9 n3r6c8 n8r6c8 +----------------------+----------------------+----------------------+ ! 48 5 7 ! 9 1 2 ! 348 348 6 ! ! 9 18 2 ! 3 4 6 ! 18 7 5 ! ! 6 14 3 ! 8 7 5 ! 2 14 9 ! +----------------------+----------------------+----------------------+ ! 5 38 1 ! 6 2 7 ! 348 9 34 ! ! 2 9 4 ! 1 3 8 ! 6 5 7 ! ! 38 7 6 ! 4 5 9 ! 138 1238#@ 123#@ ! +----------------------+----------------------+----------------------+ ! 7 34 8 ! 2 9 134 ! 5 6 134 ! ! 34 2 9 ! 5 6 134 ! 7 134 8 ! ! 1 6 5 ! 7 8 34 ! 9 234#@ 234#@ ! +----------------------+----------------------+----------------------+ DP4-2-1-OR8-relation in cells (marked #): (r9c9 r9c6 r7c9 r7c6) with 8 guardians (in cells marked @) : n3r9c9 n4r9c9 n3r9c6 n4r9c6 n3r7c9 n4r7c9 n3r7c6 n4r7c6 +-------------------+-------------------+-------------------+ ! 48 5 7 ! 9 1 2 ! 348 348 6 ! ! 9 18 2 ! 3 4 6 ! 18 7 5 ! ! 6 14 3 ! 8 7 5 ! 2 14 9 ! +-------------------+-------------------+-------------------+ ! 5 38 1 ! 6 2 7 ! 348 9 34 ! ! 2 9 4 ! 1 3 8 ! 6 5 7 ! ! 38 7 6 ! 4 5 9 ! 138 1238 123 ! +-------------------+-------------------+-------------------+ ! 7 34 8 ! 2 9 134#@ ! 5 6 134#@ ! ! 34 2 9 ! 5 6 134 ! 7 134 8 ! ! 1 6 5 ! 7 8 34#@ ! 9 234 234#@ ! +-------------------+-------------------+-------------------+ DP4-2-1-OR8-relation in cells (marked #): (r9c8 r9c6 r8c8 r8c6) with 8 guardians (in cells marked @) : n3r9c8 n4r9c8 n3r9c6 n4r9c6 n3r8c8 n4r8c8 n3r8c6 n4r8c6 +-------------------+-------------------+-------------------+ ! 48 5 7 ! 9 1 2 ! 348 348 6 ! ! 9 18 2 ! 3 4 6 ! 18 7 5 ! ! 6 14 3 ! 8 7 5 ! 2 14 9 ! +-------------------+-------------------+-------------------+ ! 5 38 1 ! 6 2 7 ! 348 9 34 ! ! 2 9 4 ! 1 3 8 ! 6 5 7 ! ! 38 7 6 ! 4 5 9 ! 138 1238 123 ! +-------------------+-------------------+-------------------+ ! 7 34 8 ! 2 9 134 ! 5 6 134 ! ! 34 2 9 ! 5 6 134#@ ! 7 134#@ 8 ! ! 1 6 5 ! 7 8 34#@ ! 9 234#@ 234 ! +-------------------+-------------------+-------------------+

As I have coded no MUG, I can't find yours.
.

Website · by **denis_berthier** » Tue Jan 14, 2025 6:36 am

.
Computations for the cbg-000 collection finished during the night. No new result:
there's no effective difference between using DP9 and DP11 in ORk-whips.
(Here, an "effective difference" is one that would change the W+DP-OR5W rating.)
Moreover, besides the example previously given, I haven't found another instance of a DP11.

(The number of guardians is restricted to 8.)
.

Website · by **denis_berthier** » Wed Jan 15, 2025 1:13 pm

.
Do you agree with the following definitions of a DP:

Definition: a deadly pattern (DP) in some resolution state RS of a consistent but possibly multi-solution Sudoku puzzle 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 there exists several different solution grids which differ only by their values in S and for which each value in a cell of 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 some of the sets in C.
.

by **Serg** » Wed Jan 15, 2025 4:05 pm

Hi, Denis!
Are you sure the DP definition from Sudopedia is unsatisfactory?

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

Serg

Website · by **denis_berthier** » Wed Jan 15, 2025 4:46 pm

.
Hi Serg
I had seen this definition. For me, it's unclear.
.

by **Serg** » Wed Jan 15, 2025 5:31 pm

Hi, Denis!
I am sorry, but for me your definition is less clear that DP definition from Sudopedia.

Serg

Website · by **denis_berthier** » Wed Jan 15, 2025 5:53 pm

.
So, here are some details that make it totally illegible.

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

Which puzzle?
What is the footprint of a solution?
The solutions have no (cell,value) pairs in common? Really?
Which puzzle?
I would have thought the 1st point was enough to have multiple solutions.
.

by **Serg** » Wed Jan 15, 2025 7:13 pm

Hi, Denis!

denis_berthier wrote:.
So, here are some details that make it totally illegible.
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. 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.

Which puzzle?

See the beginning of Sudopedia DP article:

Code: Select all: 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.

denis_berthier wrote:What is the footprint of a solution?

The term "footprint" in Sudopedia DP article contains hypertext link to Sudopedia article about footprints.

denis_berthier wrote:The solutions have no (cell,value) pairs in common? Really?

Yes, DP solutions (2 solutions exactly) have no (cell,value) pairs in common. This is well known property of strongly minimal UA sets.

denis_berthier wrote:Which puzzle?

Duplicate question.

denis_berthier wrote:I would have thought the 1st point was enough to have multiple solutions.

Yes, 1st point says: "... have multiple solutions ...". Points 2 and 3 specify additional requirements to those multiple solutions.

Not sure my understanding of your remarks is correct.

Serg

Website · by **denis_berthier** » Wed Jan 15, 2025 7:35 pm

Serg wrote:
denis_berthier wrote:The solutions have no (cell,value) pairs in common? Really?
Yes, DP solutions (2 solutions exactly) have no (cell,value) pairs in common. This is well known property of strongly minimal UA sets.

Really????? For me, they have all the values in cells outside the deadly pattern in common.

The Sudopedia "definition" is not a valid definition

But anyway, that wasn't my question.
Is my definition compatible with what you consider a DP?
.

The New Sudoku Players' Forum

Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.

Re: Unavoidable sets vs deadly patterns.