The New Sudoku Players' Forum

[denis_berthier]

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

[denis_berthier]

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

[denis_berthier]

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

[Serg]

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

[denis_berthier]

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

[Serg]

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

Serg

[denis_berthier]

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

[Serg]

Hi, Denis!

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

What is the footprint of a solution?

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

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.

Which puzzle?

Duplicate question.

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

[denis_berthier]

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

[marek stefanik]

Hi all,
deadly pattern has become an umbrella term and it is not easy to provide a single definition for all cases.

such that there exists several different solution grids which differ only by their values in S

I don't agree with this part. In valid puzzles, there are no solution grids containing the DPs.
I would say 'there exist multiple solutions of the pattern and none of them has a unique footprint' (you could require that all of them have the same footprint, if you want to exclude permeable DPs and define them separately).
A solution of a pattern (S, C) where S is a set of cells and C is a set of their candidates is a subset A of C containing one candidate of each cell in S such that no two candidates of A are in conflict.

Of course, this still doesn't cover for example BUGs which have no solution.

Marek

[denis_berthier]

such that there exists several different solution grids which differ only by their values in S

I don't agree with this part. In valid puzzles, there are no solution grids containing the DPs.

This is not what I wrote. A solution grid can only contain decided cells.

I've added a name for the puzzle to make my definition clearer:

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

I wonder if this leaves a possibility for more than two solution grids. Maybe "differ by at least one value in S" would be better. Minimality would then be used to further restrict the possibilities.
But "coincide outside S" is much simpler than any condition about the footprint and it implies it.

At this point, I don't mind to exclude BUGS from the definition. I only want something simple.
.

[Serg]

Hi, Denis!

I've added a name for the puzzle to make my definition clearer:

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

In mathematics a set contains not ordered elements, so if you want to define correspondence between 2 sets, you should say about set of pairs of elements, belonging to both sets, but not about pair of sets.

Serg

[denis_berthier]

Hi, Denis!

I've added a name for the puzzle to make my definition clearer:

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

In mathematics a set contains not ordered elements, so if you want to define correspondence between 2 sets, you should say about set of pairs of elements, belonging to both sets, but not about pair of sets.

(S, C) is a pair of sets, not a set of pairs. But you are right that I should make the correspondence S -> C more explicit (though it is obvious in this context, and not in the way you write it).
I could write more formally "the set C = {Cs, s in S}, where each Cs is the set of candidates in cell s in RS".

[Serg]

Denis,
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?

Serg

[marek stefanik]

pair (S, C) of sets – a set S of cells and the set C of their sets of candidates in RS

I missed this difference to the sudopedia's definition.
As Serg says, this might be a problem, depending on how you define a candidate.
I would define a candidate as a (digit, row, column) triple, in which case using a single set of candidates seems more sensible to me.
Using several sets would make sense if you define a candidate as just a digit, but that wouldn't work:
Consider the (non-deadly) patterns containing the candidates {1r1c1, 2r1c2} and {2r1c1, 1r1c2}. They would be indistinguishable by this definition: ({r1c1, r1c2}, {{1}, {2}}.

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.
Unless your definition of a solution grid is different from mine.

Maybe "differ by at least one value in S" would be better.

Yes, definitely.
I remember I saw this 12-cell DP where no two solutions differ in all unsolved cells.

Code: Select all

,----------,----------,--------------,
| 1   2  6 | 3  4   8 | 7    9   5   |
| 4   5  8 | 2  7   9 | 3    1   6   |
| 7   9  3 | 6  5   1 | 28   28  4   |
:----------+----------+--------------:
| 38  7  4 | 9  12  6 | 5    28  123 |
| 2   1  5 | 7  8   3 | 6    4   9   |
| 38  6  9 | 4  12  5 | 128  7   123 |
:----------+----------+--------------:
| 9   8  1 | 5  6   2 | 4    3   7   |
| 5   3  7 | 8  9   4 | 12   6   12  |
| 6   4  2 | 1  3   7 | 9    5   8   |
'----------'----------'--------------'
126348795458279316793651..4.749.65..215783649.694.5.7.981562437537894.6.642137958
126348795458279316793651284874916523215783649369425871981562437537894162642137958
126348795458279316793651824374916582215783649869425173981562437537894261642137958
126348795458279316793651824374926581215783649869415273981562437537894162642137958

Marek