The New Sudoku Players' Forum

[RW]

EDIT...it has been started !! http://www.sudopedia.org/wiki/Deadly_Pattern

I happened to read that article last week and noticed that it would need a lot of revision. I actually made my first Sudopedia edit ever and removed a completely false example, but didn't have time to change the rest of the false/bad examples, information and explanations. Personally, I'd like to see that article rewritten from scratch.

Btw. Does anyone else have problems with the Sudopedia definition?

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.

RW

[ronk]

Btw. Does anyone else have problems with the Sudopedia definition?

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 3rd statement seems incorrect. I recall seeing a deadly pattern with 3 solutions, but most of the cells had only 2 candidates. There had to be some repetition.

[edit:] As I recall, that deadly pattern looked something like ...

Code: Select all

 .   .   .   | .   .   .
 12  .   12  | .   .   .
 .   .   .   | .   .   .
-------------+------------
 123 .   12  | .   13  .
 .   .   .   | .   .   .
 13  .   .   | .   13  .

[Red Ed]

I actually made my first Sudopedia edit ever and removed a completely false example, but didn't have time to change the rest of the false/bad examples, information and explanations. Personally, I'd like to see that article rewritten from scratch.

RW, don't be a moron. Did it occur to you that someone reading (yes, me) might have spent a lot of time putting that article together and might not thank you for slating it non-constructively?

So come on, RW, raise your game and stop being a little whinger. Let's debate some changes. I know some are needed: it's why I suggested Sudopedia in the first place.

[Red Ed]

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 3rd statement seems incorrect. I recall seeing a deadly pattern with 3 solutions, but most of the cells had only 2 candidates.

Ron, that third statement is just a convention that I introduced to limit the deadly pattern to minimal cases. It doesn't lose anything for the solver to focus just on minimal cases, but it is probably bad to limit the definition this way. In other words, "deadly pattern" = first two bullets; "minimal deadly pattern" = all three.

But even that's not right. The definition needs to say something about unclued cells. It needs to be flexible enough to include UR1.1. Like I said earlier, much needs to change.

[Red Ed]

First stab at properties of a (uniqueness) deadly pattern:

• It's a collection of candidates in 4 or more cells.
• Every solution of those candidates gives rise to an exchangeable set.

"Exchangeable set" is almost equivalent to "unavoidable set", except that the latter has conventionally been limited to patterns that can be found in real solution grids.

Main purpose of (uniqueness) deadly patterns:

• If some unclued cells contain (among some of their candidates) a deadly pattern then -- assuming that the puzzle has a unique solution -- at least one other candidate in those cells must be true.

Properties that a (uniqueness) deadly pattern can have:

• Minimal. Removal of any cell or cells (not just candidates) leaves the pattern non-deadly.
• Full. Each permutation of each DP solution is, itself, a solution to the DP.
• Depleted. Not full.
• Bare. One DP candidate in each cell, i.e. the DP is an exchangeable set. This includes UR1.1.
• Closed/isolated. For each unit (row/col/box) there are as many different DP candidate values as there are cells in the DP.
• Separable. The DP cells can be split into 2 sets, each of which is itself a DP.
• Unreal. At least one DP solution cannot, in fact, ever occur in a real solution grid.
• Totally unreal. None of the DP solutions can ever occur in a real solution grid.

... and of course there'll be other properties we can think of.

I'm sure there are several small theorems to be had regarding consequences/equivalences of those definitions.

[Red Ed]

In case you thought I was taking the ****, here's a totally unreal minimal bare DP.

[RW]

Red Ed, sorry, I was not aware that this was your work... To be honest, I don't have a clue of who is usually writing those articles.

Of course I can explain what problems I found in the article. It was mainly the definition itself. The definition seemed unnecessarily complicated and I suspected it could lead to some misunderstandings. A bit down the page, my suspicions were confirmed, as there was a bad example as a direct result of the definition. This false example was caused by the second statement in the definition. This was the example:

Code: Select all

12  | 123
231 | 23
13  | 13

Which has three solutions:

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

The first two have the same footprint, but the third not, therefore the third was given as the correct unique solution... Wrong! It's an unavoidable set.

The original pattern is actually two different deadly patterns on top of each other, one of which has two candidates removed. The current Sudopedia definitions explicitly rules out these and classifies them as "not deadly", even if they are.

Because of this mistake, it seemed like the fundamentals of the article was not in place and this is why I would have liked to see it completely rewritten.

Other than the definition, there was only some minor details that seemed like outdated information, such as "all deadly patterns of size less than about 30 cells consist entirely of bivalue cells". Don't know if this really is outdated, haven't seen an example to disprove it, but you had used the number 18+ in this thread so I assumed 30 was old information.

Now you have already posted four replies in this thread while I've been writing this post... Consider this a reply to the first two, I shall take a look at your later posts next...

RW

[RW]

First stab at properties of a (uniqueness) deadly pattern:

• It's a collection of candidates in 4 or more cells.
• Every solution of those candidates gives rise to an exchangeable set.

"Exchangeable set" is almost equivalent to "unavoidable set", except that the latter has conventionally been limited to patterns that can be found in real solution grids.

Much better! This is exactly how I think of them when I use uniqueness technique!

The rest of your definitions seem really great as well. Only a few questions:

• Unreal. At least one DP solution cannot, in fact, ever occur in a real solution grid.
• Totally unreal. None of the DP solutions can ever occur in a real solution grid.

Are there any Unreal DPs that aren't Totally Unreal? This seem impossible to me by definition, but once again some monster pattern could perhaps prove me wrong...

Also, I'd like to add that any elimination made based on an unreal deadly pattern is in fact not an uniqueness elimination, but can be made also without assuming uniqueness.

RW

[JPF]

It's a shame that this interesting discussion starts (again) in the middle of a thread ...

What about these definitions :
Let be :

• G a solution grid
• A a subset of G (a subpuzzle ) ; A ⊆ G
• N(A) the number of solutions of A.
  

G is a solution grid , therefore N(G)=1
U is an unavoidable set (of G) if :

• U ⊆ G
• N(G-U)>1

U is minimal if there no unavoidable set included in U.

Two unav. U, V are equivalent (U~V) if it exists an isomorphism* f such that V=f(U).

Basically when we speak about unav. sets we are considering the quotient set UM/~
UM beeing the set of the minimal unavoidable sets on G.

First property :
a (minimal) unav. cannot be included in a unit :

It's obvious for a row or a column.
For a box, see here.

Minimum number of cells :
It follows from the remarks above that the minimum number of cells of a minimal unav. set is 4
and in that case is equivalent to this one :

Code: Select all

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


Edited, thanks to Red Ed

JPF

* ususal definition of the isomorphisms on G

[eleven]

This was the example:

Code: Select all

12  | 123
231 | 23
13  | 13

Which has three solutions ...

Am i correct, that in a valid solution process i never can arrive at this deadly pattern ?

[Red Ed]

JPF, that's not a U4. A U4 spans two of each type of unit.

eleven, yes that's right.

[eleven]

eleven, yes that's right.

Just to be clear, i mean this pattern with arbitrary extra candidates but 123's (i made it sure in the meantime to be correct). So its of no worth for solvers.

[RW]

eleven, yes that's right.

Just to be clear, i mean this pattern with arbitrary extra candidates but 123's (i made it sure in the meantime to be correct). So its of no worth for solvers.

When solving a valid puzzle, you may never arrive at this pattern:

Code: Select all

123 | 123
123 | 123
123 | 123

or any subpattern of it (pattern - n candidates). See here.

RW

[eleven]

... or any subpattern of it (pattern - n candidates). See here.

In the post you pointed to i am missing very common subpatterns like

Code: Select all

12  | 12
123 | 123
123 | 123

12  | 12
13  | 13
123 | 123


When i remember right, it was Myth, who said, that when you have such a MUG (multidigit deadly pattern), each pattern you get with placing one or more of the digits outside, is also deadly.
Now i see, that all deadly subpatterns (you can arrive at) can be found this way.
[Added: Maybe this is not correct, but i dont have the time now to verify it]
[Added2: Rubbish, i saw a triple, where there can be extra candidates Of course you possibly can arrive at the examples subset of this deadly pattern in the solution process (with extra candidates). And if one of the DP numbers can be placed, we have the UR 1.1 situation, that without assumig uniqueness we know, that one of the extra candidates must be true]