Investigation of one-band-free patterns

Everything about Sudoku that doesn't fit in one of the other sections

Re: Investigation of one-band-free patterns

Postby RW » Wed Feb 09, 2011 12:49 pm

JPF wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Investigation of one-band-free patterns

Postby ronk » Wed Feb 09, 2011 1:10 pm

RW wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Investigation of one-band-free patterns

Postby David P Bird » Wed Feb 09, 2011 3:12 pm

Withdrawn
Last edited by David P Bird on Wed Feb 09, 2011 11:34 pm, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Investigation of one-band-free patterns

Postby JPF » Wed Feb 09, 2011 7:39 pm

dobrichev wrote:Of course PT + {x} != PT ;)

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

RW wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby ronk » Wed Feb 09, 2011 7:59 pm

JPF wrote:
RW wrote: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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Investigation of one-band-free patterns

Postby RW » Wed Feb 09, 2011 8:19 pm

ronk wrote:
JPF wrote:
RW wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Investigation of one-band-free patterns

Postby JPF » Wed Feb 09, 2011 9:41 pm

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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby Serg » Thu Feb 10, 2011 12:00 am

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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby ronk » Thu Feb 10, 2011 1:25 am

Serg wrote: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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Investigation of one-band-free patterns

Postby RW » Thu Feb 10, 2011 6:20 am

JPF wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Investigation of one-band-free patterns

Postby David P Bird » Thu Feb 10, 2011 7:33 am

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.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Investigation of one-band-free patterns

Postby Serg » Thu Feb 10, 2011 9:59 am

Hi, ronk!
ronk wrote:
Serg wrote: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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby JPF » Thu Feb 10, 2011 12:40 pm

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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby David P Bird » Thu Feb 10, 2011 11:12 pm

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.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Investigation of one-band-free patterns

Postby Serg » Thu Feb 10, 2011 11:19 pm

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

David, you are a joker!
David P Bird wrote: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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

PreviousNext

Return to General