The New Sudoku Players' Forum

[RW]

May I suggest these definitions :

1. a pattern is valid if there exists at least one valid puzzle with this pattern.
a pattern that is not valid is said invalid.

If PT is invalid, every pattern PT' included in PT is invalid.

2. an invalid pattern PT is maximal if there exist {x} such that PT + {x} is a valid pattern.

This pattern is invalid maximal :

Code: Select all

+-----+-----+-----+ 
|x . .|. . .|. . .| 
|x . .|. . .|. . .| 
|x x x|. . .|. . .| 
+-----+-----+-----+ 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
+-----+-----+-----+ 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
|x x x|x x x|x x x| 
+-----+-----+-----+ 

Sounds good to me. However, should there be a separation between 1) patterns where there exist {x} such that PT + {x} is a valid pattern and 2) patterns where every {x} is such that PT + {x} is a valid pattern? The pattern above is of the second kind. The pattern below I believe is of the first kind:

Code: Select all

 *-----------*
 |...|..x|...|
 |x..|.x.|x..|
 |...|..x|x..|
 |---+---+---|
 |x.x|...|...|
 |...|...|.xx|
 |.x.|...|...|
 |---+---+---|
 |...|x..|..x|
 |...|x..|...|
 |..x|...|.x.|
 *-----------*

RW

[ronk]

However, should there be a separation between 1) patterns where there exist {x} such that PT + {x} is a valid pattern and 2) patterns where every {x} is such that PT + {x} is a valid pattern?

I think the adjective maximal makes that separation. The first could be a sub-pattern ... the 2nd a maximal sub-pattern ... but 'sub' might be a too-subtle reference to sub-puzzles.

[David P Bird]

Withdrawn

[JPF]

Of course PT + {x} != PT

Not necessarily,
If {x} ⊆ PT, then PT + {x} = PT

Sounds good to me. However, should there be a separation between 1) patterns where there exist {x} such that PT + {x} is a valid pattern and 2) patterns where every {x} is such that PT + {x} is a valid pattern?

Why not ? We could call such patterns (type 2) absolutely maximal.
The definition would be : an invalid pattern is absolutely maximal if for every {x} not included in PT, then PT + {x} is a valid pattern.

JPF

[ronk]

Sounds good to me. However, should there be a separation between 1) patterns where there exist {x} such that PT + {x} is a valid pattern and 2) patterns where every {x} is such that PT + {x} is a valid pattern?

Why not ? We could call such patterns (type 2) absolutely maximal.
The definition would be : an invalid pattern is absolutely maximal if for every {x} not included in PT, then PT + {x} is a valid pattern.

OK, I'll bite. Why would we need a definition for the "(type 1) maximal" pattern?

[RW]

Sounds good to me. However, should there be a separation between 1) patterns where there exist {x} such that PT + {x} is a valid pattern and 2) patterns where every {x} is such that PT + {x} is a valid pattern?

Why not ? We could call such patterns (type 2) absolutely maximal.
The definition would be : an invalid pattern is absolutely maximal if for every {x} not included in PT, then PT + {x} is a valid pattern.

OK, I'll bite. Why would we need a definition for the "(type 1) maximal" pattern?

I agree with ronk. Type 2 is a maximal invalid, because you cannot add another cell and still have an invalid pattern. It is also the most interesting to study I think. Type 1 is quite regular and just a basic invalid pattern IMO.

RW

[JPF]

Well, I am bit puzzled now with the type 2 invalid patterns.
This pattern is invalid maximal type 1:

Code: Select all

+-----+-----+-----+
|x . .|. . .|. . .|
|x . .|. . .|. . .|
|x x x|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x . x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

but is not a type 2 invalid pattern (see r5c5)

JPF

[Serg]

Hi, colleagues!
I am not quit ready to discuss terminology concerning maximal (exclusive/invalid) patterns. I think the term "invalid" is not quit good, because it is almost equivalent to the words "wrong", "forbidden", "erroneous", "incorrect", etc. - to the words having negative sense. But I treat considered property of patterns as useful and being worth studying.

Nevertheless I'd like to present the last part of my investigation.

Let's consider the class of patterns having 2 whole filled bands and having only one empty box in the rest band. The task to find all possible patterns combinations of boxes B1 and B2 having (or not having) valid puzzles looks much more difficult than similar task for box B1 alone, but on the contrary it is much simpler task. Thanks to coloin, published valid puzzle (thread "Two-boxes unavoidable sets" at setbb.com/sudoku forum) having 2 whole filled bands (boxes B4-B9) and having only 2 filled cells in boxes B1 and B2. I was very surprising to see such puzzle. That coloin's publication simplified my task substantially. Here is example of such valid puzzle.

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|1 . .|. . .|
|7 . .|. . .|. . .|
+-----+-----+-----+
|2 1 4|3 5 6|7 8 9|
|3 6 5|8 9 7|2 1 4|
|8 9 7|2 1 4|3 6 5|
+-----+-----+-----+
|5 3 1|4 6 2|9 7 8|
|6 4 2|9 7 8|5 3 1|
|9 7 8|5 3 1|6 4 2|
+-----+-----+-----+

The same in linear form:

Code: Select all

............1.....7........214356789365897214897214365531462978642978531978531642

So, even simplest possible pattern for non-empty boxes B1 and B2 has valid puzzles! But, obviously, if all filled cells occupy the same row, pattern has no valid puzzles (because of 2 empty rows in the band B123).

The same rule can be formulated for the class of patterns having 2 whole filled bands and having no empty boxes in the rest band.
If all filled cells are located in the same (one) row, the pattern has no valid patterns. Otherwise it has valid puzzles.
Let's find maximal patterns for the most general case, when band B123 is not empty (the band can contain no more than 2 empty boxes).
Patterns

Code: Select all

+-----+-----+-----+        +-----+-----+-----+
|x . .|. . .|. . .|        |. . x|. . .|. . .|
|x . .|. . .|. . .|        |. x .|. . .|. . .|
|x x x|. . .|. . .|        |x . .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+

are still maximal for considered (more general) class - the class of patterns having 2 whole filled bands and arbitrary the rest band. If we add 1 filled cell in the box B2 or in the box B3, the pattern will have valid puzzles (see example above). Both patterns will have valid puzzles if we'll add 1 filled cell in the box B1. So, both patterns are maximal. We must add one more maximal pattern for the considered class of pattern. It is pattern having 1 whole filled row and 2 empty rows in the band B123:

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

So, resulting "separation rule" for rather general class of patterns having 2 whole filled bands and arbitrary contents in the rest band can be formulated in a such way.

Each pattern having 2 whole filled bands and arbitrary contents in the rest band has no valid puzzles if it can be reduced to maximal exclusive patterns subset by rows/columns permutations in the B123 band. If it cannot be reduced to maximal exclusive patterns subset, it has valid puzzles.

I could find 3 maximal patterns only for the considered class of patterns (all of them are published in this post).

It is worth noting that pattern

Code: Select all

+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|. . .|. . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

having 3 empty boxes in the band B123 is subset of all 3 maximal patterns, so it has no valid puzzles (obviously).

That's all I want to say about one-band-free patterns.

Serg

[ronk]

Let's find maximal patterns for the most general case, when band B123 is not empty (the band can contain no more than 2 empty boxes).
Patterns

Code: Select all

+-----+-----+-----+        +-----+-----+-----+
|x . .|. . .|. . .|        |. . x|. . .|. . .|
|x . .|. . .|. . .|        |. x .|. . .|. . .|
|x x x|. . .|. . .|        |x . .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+

are still maximal for considered (more general) class - the class of patterns having 2 whole filled bands and arbitrary the rest band. If we add 1 filled cell in the box B2 or in the box B3, the pattern will have valid puzzles (see example above). Both patterns will have valid puzzles if we'll add 1 filled cell in the box B1. So, both patterns are maximal.

Where are proofs that (valid) puzzles do not exist for these two patterns?

[RW]

Well, I am bit puzzled now with the type 2 invalid patterns.
This pattern is invalid maximal type 1:

Code: Select all

+-----+-----+-----+
|x . .|. . .|. . .|
|x . .|. . .|. . .|
|x x x|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x . x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

but is not a type 2 invalid pattern (see r5c5)

Correct! And the interesting part of that pattern is the empty cells in band 1, they are the ones that always will include at least one unavoidable set. r5c5 is not that interesting, it's just a hidden/naked single.

RW

[David P Bird]

I feel that I'm being treated as a troll – ignore him and he'll go away eventually. But perhaps the way I expressed myself in the post I withdrew rankled, so I'll try again using more neutral wording:

We are concerned about patterns of empty cells that must inevitably contain at least one unavoidable set. That's the pattern that deserves a name "XXX".

A minimal XXX would then be one which would be destroyed if ANY of its cells are removed.

For non-minimal XXXs there will be different possibilities for destroying them depending on which cell or cells are removed. They will consist of a number of overlapping minimal XXXs. If a cell is removed that is common to all of them then the pattern would be destroyed, otherwise it will just be reduced. The minimum number of cells to be removed, N, to destroy a pattern then provides a means of characterising the non-minimal XXXs

Rather resorting to type 1 and type 2 XXXs we can then use minimal XXXs and N-XXXs to distinguish between them.

[Serg]

Hi, ronk!

Let's find maximal patterns for the most general case, when band B123 is not empty (the band can contain no more than 2 empty boxes).
Patterns

Code: Select all

+-----+-----+-----+        +-----+-----+-----+
|x . .|. . .|. . .|        |. . x|. . .|. . .|
|x . .|. . .|. . .|        |. x .|. . .|. . .|
|x x x|. . .|. . .|        |x . .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
|x x x|x x x|x x x|        |x x x|x x x|x x x|
+-----+-----+-----+        +-----+-----+-----+

are still maximal for considered (more general) class - the class of patterns having 2 whole filled bands and arbitrary the rest band. If we add 1 filled cell in the box B2 or in the box B3, the pattern will have valid puzzles (see example above). Both patterns will have valid puzzles if we'll add 1 filled cell in the box B1. So, both patterns are maximal.

Where are proofs that (valid) puzzles do not exist for these two patterns?

I've done exhaustive search for these patterns by specially written program. It would be nice to see mathematical proof of the statement that both these patterns have no valid puzzles.

Serg

[JPF]

At this point, I'd like to make some comments :

1. Congratulations to Serg for his study and the clear way he presented the results.
Btw, I came up with the same conclusions when I studied the empty boxes.
However my analysis was based on simulations and therefore I was not 100% sure about its results.
Maybe Serg could tell us how he did his exhaustive search.

2. If we add the important result first found by dukuso here that this pattern is valid :

Code: Select all

+-------+-------+-------+
| . . . | . . . | . . 8 |
| . . . | . . . | . . . |
| . . 9 | . . . | . . . |
+-------+-------+-------+
| 9 3 4 | 8 5 1 | 6 7 2 |
| 6 7 2 | 9 4 3 | 5 8 1 |
| 5 8 1 | 6 2 7 | 4 9 3 |
+-------+-------+-------+
| 4 1 3 | 5 9 2 | 8 6 7 |
| 7 2 5 | 3 6 8 | 9 1 4 |
| 8 9 6 | 7 1 4 | 2 3 5 |
+-------+-------+-------+

we now have a clearer idea on valid (and non valid )patterns full of clues in bands 2 and 3.

3. Beyond the question of terminology, there is a difficulty when we try to characterize a common property in a set of patterns.

Let P be a property of a puzzle (example : valid, minimal, non minimal, maximal,…)
There are at least 2 derived definitions for patterns:
- Weak : a pattern PT is "P" if there exist at least one puzzle having PT as pattern and having the property P
- Strong : a pattern PT is "P" if for all the puzzles having PT as pattern, the property P is true.
It may happen that the 2 definitions lead to the same partition; example P= number of clues

To be comprehensive, as Serg suggested, one can restrict the property definition to a class of patterns. His study was considering the class of patterns with full bands 2 and 3.

4. David, I can't give a feedback to your post just because I don't understand it ; what is the meaning of the words unavoidable set, destroyed, removed, overlapping minimal ?

Maybe it could be useful to open a new thread about patterns properties ?

JPF

[David P Bird]

4. David, I can't give a feedback to your post just because I don't understand it ; what is the meaning of the words unavoidable set, destroyed, removed, overlapping minimal ?

JPF, thanks for responding. I'm sorry that my writing was unclear to you.

The term unavoidable set has already been used in this thread.

I'm considering a set of empty cells that if present in a puzzle grid will mean that it can never have a unique solution. Suppose we call that pattern a "dastardly puzzle blocker" not that I'm suggesting that term, but it may make it easier than using "XXX" as I did before. Now if cells are subtracted (or removed) from such a pattern at some point it will cease to be a dastardly puzzle blocker (or in other words it will be destroyed).

I defined the term "minimal" as applied to dastardly puzzle blockers in my previous post.

If we have two minimal puzzle blockers that have some cells in common they can be considered to overlap at those cells and can be called overlapping minimal DPBs

Every time we coin new terms we add to the confusion and my aim was to minimise that firstly by making them more memorable, and secondly by focusing on the smaller of the two complementary patterns as they appear in the full puzzle grid, which is probably where any further studies would lead us.

[Serg]

I feel that I'm being treated as a troll – ignore him and he'll go away eventually.

David, you are a joker!

We are concerned about patterns of empty cells that must inevitably contain at least one unavoidable set. That's the pattern that deserves a name "XXX".

A minimal XXX would then be one which would be destroyed if ANY of its cells are removed.

For non-minimal XXXs there will be different possibilities for destroying them depending on which cell or cells are removed. They will consist of a number of overlapping minimal XXXs. If a cell is removed that is common to all of them then the pattern would be destroyed, otherwise it will just be reduced. The minimum number of cells to be removed, N, to destroy a pattern then provides a means of characterising the non-minimal XXXs

Rather resorting to type 1 and type 2 XXXs we can then use minimal XXXs and N-XXXs to distinguish between them.

I see a problem in your approach (maybe I am wrong). Minimal XXX is also 1-XXX, because it needs 1 additional cell to be broken. But non-minimal XXX can also be qualified as 1-XXX. So, if my understanding is right, proposed classification can confuse minimal XXX and non-minimal XXX.

I think it would be better to count maximal possible number of cells which can be removed leaving XXX as XXX. Then minimal XXXs are also 0-XXXs. But non-minimal XXX will be 1-XXX, 2-XXX, ..., N-XXX (N > 0).

Serg