Hi, people!
I'd like to introduce new type of sudoku patterns - minimal patterns.
Minimal pattern has valid sudoku puzzles, but cannot be decreased by deleting filled cells provided that this pattern still must have valid puzzles. I.e. if we'll remove any cell from this pattern, it will have no valid puzzles.
Minimal patterns are opposite to maximal patterns. Maximal patterns have no valid patterns and cannot be increased by adding clues provided they must retain the property non having valid puzzles. Minimal patterns, on the contrary, have valid patterns and cannot be decreased by deleting clues provided they must retain the property having valid puzzles.
Minimal patterns have interesting property - they have minimal valid puzzles only. On the contrary, it is easy to prove, that pattern having minimal valid puzzles only is minimal.
Minimal patterns are not so rare - all known at the moment 33883 17-clue patterns having valid puzzles are minimal. All 121 vertically symmetric patterns having valid puzzles are minimal, and 44 of 48 double diagonal symmetric patterns are minimal too. The higher given number of clues in a pattern, it is more difficult to find minimal pattern containing such number of clues.
Minimal patterns can be useful during exhaustive search for valid puzzles. Each pattern being subset of some minimal pattern cannot have valid puzzles. For example, all known minimal symmetric 18-clue patterns (165 = 121 + 44) excludes appox. 18 x 165 = 2970 17-clue patterns from exhaustive search for valid 17-clue puzzles. Not so many patterns can be excluded in this case (this number is really substantially less because of isomorphs), but if we could find minimal patterns containing more cells, they would be more useful.
Serg
[Edited. I corrected typos.]
Minimal patterns
16 posts
• Page 1 of 2 • 1, 2
Minimal patterns
by Serg » Fri Oct 10, 2014 7:14 am
Last edited by Serg on Mon Oct 27, 2014 6:20 pm, edited 1 time in total.
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
Re: Minimal patterns
by GouinJP » Fri Oct 10, 2014 9:24 am
Hello
Could you provide examples?
Thank you
.
Could you provide examples?
Thank you
.
- GouinJP
- Posts: 296
- Joined: 06 April 2013
- Location: Montreal
Re: Minimal patterns
by Serg » Fri Oct 10, 2014 12:20 pm
Hi, GouinJP!
I don't quite understand, what kind of example do you want to see. Anyway, Afmob wrote in his post (December 11, 2013) in the thread Symmetric 18s:
This puzzle is minimal (I checked its minimality). One should sustitute each number in this puzzle by "1" to get minimal pattern:
Serg
GouinJP wrote:Could you provide examples?
I don't quite understand, what kind of example do you want to see. Anyway, Afmob wrote in his post (December 11, 2013) in the thread Symmetric 18s:
Afmob wrote:I just found another new pattern with one valid puzzle.
- Code: Select all
...........1...2...2..3..4.....5.......142...6.......7...6.4...8.......17...9...6
This puzzle is minimal (I checked its minimality). One should sustitute each number in this puzzle by "1" to get minimal pattern:
- Code: Select all
...........1...1...1..1..1.....1.......111...1.......1...1.1...1.......11...1...1
Serg
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
Re: Minimal patterns
by dobrichev » Fri Oct 10, 2014 3:55 pm
Hi Serg,
I worry that such a search would have melted the polar ice.
Of course some interesting, probably highly symmetric patterns, may appear.
What about the maximal pattern(s) where all combinations of values are extendable to valid solution grid? Obviously with <= 1 position in a house.
I worry that such a search would have melted the polar ice.
Of course some interesting, probably highly symmetric patterns, may appear.
What about the maximal pattern(s) where all combinations of values are extendable to valid solution grid? Obviously with <= 1 position in a house.
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Minimal patterns
by Serg » Fri Oct 10, 2014 4:52 pm
Hi, Mladen!
What do you mean? The main part of known maximal patterns was presented in the thread Investigation of one-crossing-free patterns (so called "40-patterns list").
Serg
dobrichev wrote:What about the maximal pattern(s) where all combinations of values are extendable to valid solution grid? Obviously with <= 1 position in a house.
What do you mean? The main part of known maximal patterns was presented in the thread Investigation of one-crossing-free patterns (so called "40-patterns list").
Serg
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
Re: Minimal patterns
by dobrichev » Sat Oct 11, 2014 4:53 am
Yes, this was great job.
Take this patern
It can be completed to valid solution grid for any A in {1..9}.
Now take this
It it can be completed for all ABCDEFGHI in {111111111, 111111112, ... 999999999} then this is the only maximal pattern.
If it can't, then there are one or more sub-patterns in between that are completable. Those with the maximal number of positions are the answer.
I know this is totally offtopic and maybe absolutely useless. Withdraw it?
Take this patern
- Code: Select all
+-------+-------+-------+
| A . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
It can be completed to valid solution grid for any A in {1..9}.
Now take this
- Code: Select all
+-------+-------+-------+
| A . . | . . . | . . . |
| . . . | B . . | . . . |
| . . . | . . . | C . . |
+-------+-------+-------+
| . D . | . . . | . . . |
| . . . | . E . | . . . |
| . . . | . . . | . F . |
+-------+-------+-------+
| . . G | . . . | . . . |
| . . . | . . H | . . . |
| . . . | . . . | . . I |
+-------+-------+-------+
It it can be completed for all ABCDEFGHI in {111111111, 111111112, ... 999999999} then this is the only maximal pattern.
If it can't, then there are one or more sub-patterns in between that are completable. Those with the maximal number of positions are the answer.
I know this is totally offtopic and maybe absolutely useless. Withdraw it?
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Minimal patterns
by Serg » Sat Oct 11, 2014 5:31 pm
Hi, Mladen!
I am not sure that my understanding is right. Do you propose to investigate all completable combinations of numbers placed in A,B, ..., I cells?
But it is evident that combination A=1, B=2, C=2, D=2, G=2 has internal contradiction and cannot be completed. And what relation is between this 9-cell configuration and patterns maximality? Please, clarify your point.
Serg
dobrichev wrote:
- Code: Select all
+-------+-------+-------+
| A . . | . . . | . . . |
| . . . | B . . | . . . |
| . . . | . . . | C . . |
+-------+-------+-------+
| . D . | . . . | . . . |
| . . . | . E . | . . . |
| . . . | . . . | . F . |
+-------+-------+-------+
| . . G | . . . | . . . |
| . . . | . . H | . . . |
| . . . | . . . | . . I |
+-------+-------+-------+
It it can be completed for all ABCDEFGHI in {111111111, 111111112, ... 999999999} then this is the only maximal pattern.
I am not sure that my understanding is right. Do you propose to investigate all completable combinations of numbers placed in A,B, ..., I cells?
But it is evident that combination A=1, B=2, C=2, D=2, G=2 has internal contradiction and cannot be completed. And what relation is between this 9-cell configuration and patterns maximality? Please, clarify your point.
Serg
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
Re: Minimal patterns
by dobrichev » Sun Oct 12, 2014 8:07 pm
Right, ABCDG can't be populated with all possible 1..9.
Can ABCDEF?
I thinked a bit more on your original proposal for the minimal patterns. The relationship with the "maximal sub-patterns" is that if any pattern has such sub-pattern, the positions covered by the subpattern don't truncate itselves the search space in any way. In the nested loops, the maximal sub-patterns are the worst candidates for iteration in the outer loops.
A possible startpoint for minimal patterns search is adding a cell to the patterns at {-2+2} to the known 17s where we know there are no valid puzzles. IMO generating a huge collection of 18s would be a better approach but with still too many patterns to investigate for minimality. Too ambitious for today's computational resources.
Can ABCDEF?
I thinked a bit more on your original proposal for the minimal patterns. The relationship with the "maximal sub-patterns" is that if any pattern has such sub-pattern, the positions covered by the subpattern don't truncate itselves the search space in any way. In the nested loops, the maximal sub-patterns are the worst candidates for iteration in the outer loops.
A possible startpoint for minimal patterns search is adding a cell to the patterns at {-2+2} to the known 17s where we know there are no valid puzzles. IMO generating a huge collection of 18s would be a better approach but with still too many patterns to investigate for minimality. Too ambitious for today's computational resources.
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Minimal patterns
by coloin » Sun Oct 12, 2014 10:14 pm
A while back ...i investigated the number of ED ways to populate a template/rookery all possible [valid] ways.
symmetry reductions resulted in the 9,8,and 7 clue [2 types] all < 800 [from memory]
probably lost on the programmers forum - as i cant find the post.
are you saying that this is an inefficient way to search a pattern ?
anyway ...... what % of 18 clue patterns have a valid puzzle anyway ?
this 19-clue puzzle almost certainly has a minimal pattern.....
giving 18-clue and 17-clue patterns without puzzles.
C
symmetry reductions resulted in the 9,8,and 7 clue [2 types] all < 800 [from memory]
probably lost on the programmers forum - as i cant find the post.
are you saying that this is an inefficient way to search a pattern ?
anyway ...... what % of 18 clue patterns have a valid puzzle anyway ?
this 19-clue puzzle almost certainly has a minimal pattern.....
- Code: Select all
13.......7.....5.......48.....123......4561.......9.....8..............7....7..36
giving 18-clue and 17-clue patterns without puzzles.
C
- coloin
- Posts: 2384
- Joined: 05 May 2005
- Location: Devon
Re: Minimal patterns
by coloin » Mon Oct 13, 2014 11:48 am
And thinking about it a bit more ......
Every valid 18-clue puzzle and pattern will have 63 non-minimal 19-clue patterns
That would tend to make a 20-clue minimal pattern quite rare ?
C
Every valid 18-clue puzzle and pattern will have 63 non-minimal 19-clue patterns
That would tend to make a 20-clue minimal pattern quite rare ?
C
- coloin
- Posts: 2384
- Joined: 05 May 2005
- Location: Devon
Re: Minimal patterns
by Serg » Tue Oct 14, 2014 8:01 am
Hi, colleagues!
If my calculations are correct, this 23-clue pattern (subset of Fractal Pattern) is minimal.
This patterns has 3 valid puzzles, all are minimal. Here they are (in canonic form):
Serg
If my calculations are correct, this 23-clue pattern (subset of Fractal Pattern) is minimal.
- 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|
+-----+-----+-----+
This patterns has 3 valid puzzles, all are minimal. Here they are (in canonic form):
- Code: Select all
........1......23.......45...1..6....2..4....74.58......9..3...43.86....86.75....
........1......23.......45...1..6....2..4....74.85......9..3...46.78....83.56....
........1......23.......45...1..6....2..5....7.34.2....3..8....4.26.7...9.72.3...
Serg
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
Re: Minimal patterns
by blue » Tue Oct 14, 2014 9:36 pm
If what I wrote here is correct, then this is another minimal pattern.
Only 19 clues though, unfortunately ... and 16 automorohisms as well.
- Code: Select all
. x . | . x . | . x .
x . . | x . . | x . .
. . . | . . . | . . .
------+-------+------
. x . | . x . | . x .
x . . | x . . | x . .
. . . | . . . | . . .
------+-------+------
. x . | . x . | . x .
x . . | x . . | x . .
. . . | . . . | . . x
Only 19 clues though, unfortunately ... and 16 automorohisms as well.
- blue
- Posts: 979
- Joined: 11 March 2013
Re: Minimal patterns
by Serg » Thu Oct 16, 2014 7:53 am
Hi, blue!
Interesting result! Could you publish all found 379 puzzles?
I see no ways of practical usage of minimal patterns at the moment. 49157 known minimal 17-clue puzzles seem to be useful during 39/40-clue minimal puzzles search. They can potentially exclude huge amount of 39/40-clue candidate puzzles, but I don't see effective algorithm to check all those 49157 subpuzzles during 39/40-clue puzzles generation.
I spent a half of year for studying Graph Theory to find simple check procedure which can show validity of a pattern without usual brute-force generation and solving puzzle. Sudoku puzzle can be reduced to a graph having order not more than 73. If this graph is uniquely colorable, then sudoku puzzle is valid. Simple criteria of unique colorability are known, but they are too weak for practical usage.
So, I am returning to "brute-force" search and still hope to develope universal procedure which can do fast exhaustive search for valid patterns (puzzles).
Serg
[Edited. I corrected typos.]
blue wrote:If what I wrote here is correct, then this is another minimal pattern.
- Code: Select all
. x . | . x . | . x .
x . . | x . . | x . .
. . . | . . . | . . .
------+-------+------
. x . | . x . | . x .
x . . | x . . | x . .
. . . | . . . | . . .
------+-------+------
. x . | . x . | . x .
x . . | x . . | x . .
. . . | . . . | . . x
Only 19 clues though, unfortunately ... and 16 automorohisms as well.
Interesting result! Could you publish all found 379 puzzles?
I see no ways of practical usage of minimal patterns at the moment. 49157 known minimal 17-clue puzzles seem to be useful during 39/40-clue minimal puzzles search. They can potentially exclude huge amount of 39/40-clue candidate puzzles, but I don't see effective algorithm to check all those 49157 subpuzzles during 39/40-clue puzzles generation.
I spent a half of year for studying Graph Theory to find simple check procedure which can show validity of a pattern without usual brute-force generation and solving puzzle. Sudoku puzzle can be reduced to a graph having order not more than 73. If this graph is uniquely colorable, then sudoku puzzle is valid. Simple criteria of unique colorability are known, but they are too weak for practical usage.
So, I am returning to "brute-force" search and still hope to develope universal procedure which can do fast exhaustive search for valid patterns (puzzles).
Serg
[Edited. I corrected typos.]
Last edited by Serg on Mon Oct 27, 2014 6:13 pm, edited 1 time in total.
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
Re: Minimal patterns
by blue » Thu Oct 16, 2014 9:41 am
Serg wrote:Interesting result! Could you publish all found 379 puzzles?
I still had them lying around.
Lucky me
Hidden Text: Show
- blue
- Posts: 979
- Joined: 11 March 2013
Re: Minimal patterns
by Serg » Thu Oct 16, 2014 11:47 am
Hi, blue!
Thanks for posted 379 puzzles!
Serg
Thanks for posted 379 puzzles!
Serg
- Serg
- 2018 Supporter
- Posts: 860
- Joined: 01 June 2010
- Location: Russia
16 posts
• Page 1 of 2 • 1, 2
