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 Serg » Thu Feb 10, 2011 11:46 pm

Hi, JPF!
JPF wrote: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.

Thank you for your words and for very interesting link. I've already read thread "Empty boxes I" earlier. It is well-known fundamental thread, containing very important information. But the last link ("Minimal number of clues" thread) is new to me. It looks like one of the first discussion on sudoku properties. Very interesting!
Certainly I'll describe my method (maybe today, if I'll not get asleep).
JPF wrote: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

I like your approach. It looks like "strongly minimal" or "weakly minimal" unavoidable sets as they were determined years ago by Red Ed.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby dobrichev » Fri Feb 11, 2011 12:11 am

An exhaustive search for discussed patterns is not difficult to be done.
Each valid puzzle consists of a valid grid solution and sufficient clues to hit all unavoidable sets in the solution grid.
Having bands 2 and 3 populated we know that all unavoidables are hit, except those lying entirely in band 1.
Also we know the band 1 is one of the known 416 essentially different bands.
So we have to determine the unavoidable sets in each of the 416 bands, and find the possible ways to hit them (minimally).
Note that this task does not depend of the actual content of the entirely populated bands 2 and 3.

For each band N, we can:
- generate a grid having band N at the top. Say, by creating a puzzle with 27 givens corresponding to the known cells in the band, and then finding its first solution.
- find grid's UA sets for its first band. Say, by creating a puzzle from the previously generated grid with 54 givens in bands 2 and 3, then finding all its solutions, comparing them to original grid, storing differences as unavoidable sets, and finally filtering out non-minimal UA. The cell positions for the UA found are property of the band (all one-band UA in all 416 bands have only 2 permutations), and hitting them is necessary for all band's completions.
- find the minimum amount of clues which hit all minimal unavoidable sets, using brute force.

Here is an example for band 27.
Code: Select all
123456789456789231789123645 #band 27
123456789456789231789123645214365897365897124897214356531642978642978513978531462 #a grid with band 27
...........................214365897365897124897214356531642978642978513978531462 #the completion

The completion has 96 solutions due to unhit UA in the following 56 unavoidable sets
Hidden Text: Show
Code: Select all
1..4.....4..7.....7..1...........................................................
.2..5.....5..8.....8..2..........................................................
..3..6.....6..9.....9..3.........................................................
1....67.94....9.317....364.......................................................
.2.4..78..5.7..2.1.8.1...45......................................................
..3.5..89..6.8.23...9.2.6.5......................................................
123456789456789231...............................................................
123456789.........789123645......................................................
12345678..56.8.23.7..1.364.......................................................
1234567.945.7..2.1..9.236.5......................................................
123456.894.6..9.31.8.12..45......................................................
123456...456...231...123645......................................................
12345.78945.789231..9..3.........................................................
12345..894....9.31.89123.45......................................................
1234.67894.6789231.8..2..........................................................
1234.678...6.8.23.78.12364.......................................................
1234..7894..789231.89.23.........................................................
123.56789.567892317..1...........................................................
123.567.9.5.7..2.17.91236.5......................................................
123.5.789.5.7892317.91.3.........................................................
123..6789..678923178.12..........................................................
123...789456...231789...645......................................................
123...789...789231789123.........................................................
12.456789..6..9...78912.645......................................................
12.4567.94567.92.1..9.2.6.5......................................................
12.45.78..56.8923.7.91.364.......................................................
12.45....456..9231..9123645......................................................
12.4..78...6.8923.78912364.......................................................
12..567.9.567.92.17.912.6.5......................................................
1.3456789.5..8....7891.3645......................................................
1.3456.89456.89.31.8.1...45......................................................
1.345..8945..89.31.891.3.45......................................................
1.34.67.945.78.2.1.89.236.5......................................................
1.34.6...456.8.231.8.123645......................................................
1.3..67.9.5.78.2.17891236.5......................................................
1..456789.56.89...7891..645......................................................
1..4.67.94567892.1.89.2.6.5......................................................
1..4.....456.89231.89123645......................................................
1....67.9.567892.178912.6.5......................................................
.234567894..7.....789.23645......................................................
.2345678.45678.23.7....364.......................................................
.234.678.4.678.23.78..2364.......................................................
.23.56.894.67.9.3178.12..45......................................................
.23.56...4567..2317..123645......................................................
.23.5..894..7.9.31789123.45......................................................
.2.4567894.67.9...789.2.645......................................................
.2.45.78.45678923.7.9..364.......................................................
.2.4..78.4.678923.789.2364.......................................................
.2..5....4567.92317.9123645......................................................
..345678945.78....789..3645......................................................
..3.56.89456789.3178.1...45......................................................
..3.5..8945.789.317891.3.45......................................................
..3..6...45678.23178.123645......................................................
...456789456789...789...645......................................................
...456789...789231...123645......................................................
.........456789231789123645......................................................

The first 3 UA are disjoint, which requires absolute minimum of 3 additional clues.
Using brute force, we can find that it is not possible to hit all UA with 3 clues, but for 4 clues there are 1053 different ways to do it.
Here are some of them
Code: Select all
.2.......4.6.........1.....
.2.4.......6......7........
12.........67..............
.2.........6.8....7........
.2.......4.6.8.............

We can collect all possible ways to determine all 416 bands.
Further we can process the data and claim "there is at least one band which can be completed in this way", etc.

The above is only a clarification of the one of the possible ways to do what Serg already did. Well done, Serg.

MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Investigation of one-band-free patterns

Postby coloin » Fri Feb 11, 2011 2:22 pm

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

................

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


Well it should be possible to prove that there is always an unavoidable set in these empty positions - no matter what the band

Code: Select all
+---+---+---+
|...|123|...|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 456789    456789    456789    | 1         2         3         | 456789    456789    456789    |
| 123789    123789    123789    | 4         5         6         | 123789    123789    123789    |
| 123456    123456    123456    | 7         8         9         | 123456    123456    123456    |
+-------------------------------+-------------------------------+-------------------------------+

Essentially different / equivalent for our purpose ways to fill in B2 and B3 cant be many [is it 44 ?]
Number of ways to fill 4 or 6 clues in B 1 cant be that many either

braid or rope pattern
Code: Select all
+----------------------------+----------------------------+----------------------------+
| 789      789      789      | 1        2        3        | 4        5        6        |
| 123789   123789   123789   | 4        5        6        | 123789   123789   123789   |
| 4        5        6        | 7        8        9        | 123      123      123      |
+----------------------------+----------------------------+----------------------------+
or
+-------------------------------+-------------------------------+-------------------------------+
| 6         789       789       | 1         2         3         | 4         5         789       |
| 123789    123789    123789    | 4         5         6         | 123789    123789    123789    |
| 12345     12345     12345     | 7         8         9         | 1236      1236      1236      |
+-------------------------------+-------------------------------+-------------------------------+


oops MD has just said this !

so to "prove" that a pattern is impossible
generate all the essentially different ways to fill the patterns spaces
generate a puzzle for each of these reciprocal patterns
remove the reciprocal clues from each and check that all indeed have more than 1 solution.

This pattern i believe doesnt have puzzles too

Code: Select all
+---+---+---+
|...|...|...|
|.2.|...|...|
|..1|847|532|
+---+---+---+
|..8|123|749|
|..2|456|381|
|..3|789|625|
+---+---+---+
|..7|634|298|
|..9|275|163|
|..6|918|457|
+---+---+---+    3 solutions

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Investigation of one-band-free patterns

Postby dobrichev » Fri Feb 11, 2011 6:59 pm

For the record, band 1 has 7 802 998 272 valid completions, and band 27 has 7 004 355 840.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Investigation of one-band-free patterns

Postby David P Bird » Fri Feb 11, 2011 9:40 pm

Serge thank you for your response too. I'm fighting a lost cause here so I'm not going to pursue it further. However I feel I owe it to you to respond to your point:
Serg wrote: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.

It's true that every minimal XXX is also a 1-XXX but not the other way around, and I was aware of that when suggested it. However I considered that as for UAs, lines of reasoning would either be confined just to minimal XXXs or any type of XXX, and that the minimum rather than the maximum number of givens needed to disrupt one would be the more useful measure.

Rather than having to resort adding 'weak' or 'strong' to define what type of minimal we were discussing, a minimal XXX would always be strong and a 1-XXX wouldn't necessarily be strong.
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Investigation of one-band-free patterns

Postby David P Bird » Fri Feb 11, 2011 11:00 pm

RW on page 1 wrote:You could also say that any box pattern that isn't a subset of any of the two following patterns have valid puzzles:
Code: Select all
..x  x..
.x.  x..
x..  xxx

This can be further simplified to "any box pattern that has a) at least four filled cells, and b) no rectangle of empty cells has valid puzzles".
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Investigation of one-band-free patterns

Postby Serg » Sat Feb 12, 2011 12:02 am

Hello, David!
David P Bird wrote:
RW on page 1 wrote:You could also say that any box pattern that isn't a subset of any of the two following patterns have valid puzzles:
Code: Select all
..x  x..
.x.  x..
x..  xxx

This can be further simplified to "any box pattern that has a) at least four filled cells, and b) no rectangle of empty cells has valid puzzles".

What do you mean? Does "minidiagonal" box pattern really have any rectangle of empty cells?

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby David P Bird » Sat Feb 12, 2011 12:04 am

Serg wrote:Hello, David!
David P Bird wrote:
RW on page 1 wrote:You could also say that any box pattern that isn't a subset of any of the two following patterns have valid puzzles:
Code: Select all
..x  x..
.x.  x..
x..  xxx

This can be further simplified to "any box pattern that has a) at least four filled cells, and b) no rectangle of empty cells has valid puzzles".

What do you mean? Does "minidiagonal" box pattern really have any rectangle of empty cells?

Serg

It passes condition b) but fails condition a)!!!!
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Re: Investigation of one-band-free patterns

Postby Serg » Sat Feb 12, 2011 2:46 am

Hi, people!
dobrichev, thank you for your help! The task of doing exhaustive search for the pattern having 2 whole filled bands and the rest band with 2 empty boxes and one non-empty box, which must contain given clue's configuration, is not so complicated. You described surely possible method of searching. I used similar, but slightly different method.

First of all, if a pattern has 2 different puzzles which have the same completions (variants of empty cells filling), those puzzles have the same number of solutions with the same completitions. (It can be proved.) So, it is not necessary to check out all possible puzzles for given pattern. It is sufficient to check out (does a puzzle have unique or multiple solutions?) puzzles having different completions only. For a given completion it is sufficient to check out arbitrary puzzle having this completion, because all puzzles of the same pattern having the same completions have the same number of solutions.

It is convenient to study completions for patterns considered because these patterns have large number of filled cells (54+). If a pattern would have less than a half of grid cells (40 or less cells), it would be more convenient to check out puzzles instead of completions.

Overall procedure of exhaustive search for puzzles having unique solutions (for given pattern) should looks like the following.

1. Loop over all completions (partially filled band B123).
2. For each completion we must find solution grid treating completion's cells as clues and other cells - as empty cells.
3. Found solution then should be transformed to a puzzle by setting empty all cells not participating the pattern.
4. Then we should find solutions (no more than 2 solutions) of the produced puzzle.
5. If the produced puzzle has unique solution - given pattern has valid puzzles, if it has multiple solutions (2 solutions at least) we should go to the step 1 to consider next completion.

Band B123 of any solution grid can be transformed to lexicographical order (see article "Mathematics of Sudoku I" by Bertram Felgenhauer and Frazer Jarvis). So, we can consider not completions, but whole filled bands B123:
Code: Select all
+-----+-----+-----+
|1 2 3|4 A B|C D E|
|4 5 6|x x x|x x x|
|7 8 9|x x x|x x x|
+-----+-----+-----+

where A > 4, B > A, D > C, E > D.
It is well known that there are 36288 non-isomorphic such band configurations (see "Mathematics of Sudoku I").

Refined procedure of exhaustive search for puzzles having unique solutions for given pattern consists of 2 parts.

Part 1
1. Loop over 36288 non-isomorphic lexicographically ordered band configurations.
2. For each band configurations find solution grid treating band's cells as clues and other cells - as empty cells. Write to the file all solution grids (36288).

Both steps are done by simple backtracking solver. This procedure takes less than 1 second.

Part 2
3. Read solution grids from the file.
4. Tansform each solution grid to a puzzle by setting empty all cells not participating the pattern.
5. Find solutions (no more than 2 solutions) of the puzzle. (Done by simple backtracking solver.)
6. If the puzzle has unique solution - given pattern has valid puzzles, if the puzzle has multiple solutions (2 solutions at least) - continue loop - go to the step 3.

This procedure takes about 1 second.

Surely it is possible to use 416 band configurations, but this approach has some disadvantages. For example, instead of using permanent box B1 pattern, we must check out 6 x 6 = 36 variants of box pattern (to account for all possible rows/columns permutations in the box B1). Additionally we must repeat this procedure for all 3 boxes (B1, B2, B3). So, 416 variants transformes to 36 x 3 x 416 = 44928 variants (slightly more than 36288).

When box pattern has some symmetry, we can reduce number of generated solution grid several times. But it is not worth doing because of short execution time of the program.

When I've done exhaustive search for the pattern having 2 whole filled bands and the rest band with 1 empty box and 2 boxes containing only 1 filled cell each, I could not use lexicographically ordered band because r2c4 clue prohibits swapping boxes B2/B3 and swapping column c4 with c5/c6 columns. So, we have such band B123 configuration.
Code: Select all
+-----+-----+-----+
|1 2 3|x A B|C D E|
|4 5 6|x x x|x x x|
|7 8 9|x x x|x x x|
+-----+-----+-----+

where B > A, D > C, E > D.
There are 217728 such configurations. We can reduce this number twice by rejecting isomorphic configurations because of possible swapping columns c2/c3 and relabelling (to restore right digits order in the box B1). Program execution time - less 5 seconds.

Serg

Edited: I corrected some typos.
Last edited by Serg on Sat Feb 12, 2011 12:56 pm, edited 2 times in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-band-free patterns

Postby JPF » Sat Feb 12, 2011 9:52 am

Serg,
I'm probably missing something.
you wrote: First of all, if a pattern has 2 different valid puzzles which have the same completitions (variants of empty cells filling), those puzzles have the same number of solutions with the same completitions. (It can be proved.)

If the puzzles are valid, don't they have only 1 solution ?
What is a completition ? If you mean "completion", I don't really understand why the word solution is not used instead.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-band-free patterns

Postby Serg » Sat Feb 12, 2011 12:45 pm

Hi, JPF!
JPF wrote:Serg,
I'm probably missing something.
you wrote: First of all, if a pattern has 2 different valid puzzles which have the same completitions (variants of empty cells filling), those puzzles have the same number of solutions with the same completitions. (It can be proved.)

If the puzzles are valid, don't they have only 1 solution ?

You are right. I cannot call those puzzles valid, because they can have multiple solutions. (I'll edit my post.)
JPF wrote:What is a completition ? If you mean "completion", I don't really understand why the word solution is not used instead.

You are right again - I meant "completion", of course. Sorry, my English is not perfect. But the term "solution" cannot be used in this case, because I mean subgrid, completed original puzzle. Let P - puzzle, G - its (valid) solution grid. Then "completion", C = G - P. I mean that 2 different puzzles of the same pattern have different solution grids, but these grid coincide for all cells placed outside the puzzles pattern.

Thank you for correction!

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Postby Afmob » Fri Apr 20, 2012 2:39 pm

I can confirm that the two patterns Serg mentioned have no valid puzzle. I think it's important to validate those result by a different source before applying them to a different proof.

The diagonal pattern has 6,132 essentially different completions (432 automorphisms) and the empty rectangle pattern has 1,582 essentially different completions (288 automorphisms).
Afmob
 
Posts: 130
Joined: 28 June 2011

Previous

Return to General