Within the first 100000 patterns in this order only 4 (of the 107) are known to have a unique puzzle (starting with line 20324). So here there might be some potential to exclude patterns directly.
Afmob, i got the same number of 4693836890 e-d puzzles in your example above. Also our program/cpu peformance seems to be similar. I stopped searching having solved about the half after 13 hours. However on a 64bit OS using Mladens solver instead of Brian Turner's should be noticeably faster.
I have started to scan the patterns for there number of automorphisms. After a 4th of them i got about 36% with 4 morphs, 44 % with 8 and 20 % with 12+.
I cant see much room for optimizations. I hoped, that the similarity of consecutive puzzles to check could help. So i thought, it should be faster, when the solver does not guess the first digit in the cell, but the digit of the last solution (if there was one and if it is still available). But - it was sligthly slower.
Symmetric 18s
by Afmob » Fri Apr 20, 2012 10:08 am
I did not actually test how long it would take to solve all those puzzles with JSolve. I just estimated the time with 60,000 Sudokus solved per second which is based on 16 clues Sudokus, so the actual speed should be faster since there are more clues and (in general) less guessing is involved. By the way, I will let the cluster run over the weekend and see how many patterns get analyzed.
- Afmob
- Posts: 132
- Joined: 28 June 2011
Re:
by Serg » Fri Apr 20, 2012 10:40 am
Hello, Afmob!
What a nice pattern you published!
It resembles me palace. But unfortunately this pattern have no valid puzzles, because it is subset of the pattern
(see the thread Investigation of one-band-free patterns on this forum). This is one of the ideas that I am planning to implement - statement "pattern has no valid puzzles if it has 2 empty boxes in a band (stack) and if the third box in the same band (stack) has less than 4 clue" is true, but it is not complete, because some configurations of the third box containing 4 or even 5 clues has no valid puzzles too (see thread cited above).
Serg
[Edited: I corrected a typo.]
Afmob wrote:I've analyzed the first 658 patterns of the new list and none of them have a uniquely solvable 18 clues Sudoku. As you can see the filtered list takes much longer than the original list. So every pattern before
- Code: Select all
.............1.......111................1......11111............1.1.1.1..11...11.
can be omitted.
What a nice pattern you published!
- Code: Select all
. . . . . . . . .
. . . . 1 . . . .
. . . 1 1 1 . . .
. . . . . . . . .
. . . . 1 . . . .
. . 1 1 1 1 1 . .
. . . . . . . . .
. 1 . 1 . 1 . 1 .
. 1 1 . . . 1 1 .
It resembles me palace. But unfortunately this pattern have no valid puzzles, because it is subset of the 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 x x|x x x|
+-----+-----+-----+
(see the thread Investigation of one-band-free patterns on this forum). This is one of the ideas that I am planning to implement - statement "pattern has no valid puzzles if it has 2 empty boxes in a band (stack) and if the third box in the same band (stack) has less than 4 clue" is true, but it is not complete, because some configurations of the third box containing 4 or even 5 clues has no valid puzzles too (see thread cited above).
Serg
[Edited: I corrected a typo.]
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
UA vs digit guesses
by eleven » Sat Apr 21, 2012 7:55 am
The next pattern i looked at was the first one, which has a puzzle with a unique solution.
There is no other than the known valid puzzle in it.
It has less than 8 % zero solution puzzles. I saw, that there is some probability, that a multi solution puzzle has a solution with a 4 cell UA in the cells marked with @.
So i tried to add 2 UA digits (i just took the first 2 in the c28 cells different to those in the Y cells) and solve it in a first step. It is sufficient to find a single solution then to know, that the puzzle has multiple solutions. This happened for about 25 % of the puzzles.
Though this way i had 75 % more solver calls, the search was 4.5 % faster.
Now this will not help us much for the symm. 18 clue search, and maybe this trick is already used in some solvers (for low clue puzzles).
There is no other than the known valid puzzle in it.
It has less than 8 % zero solution puzzles. I saw, that there is some probability, that a multi solution puzzle has a solution with a 4 cell UA in the cells marked with @.
- Code: Select all
+-------+-------+-------+
| @ . . | . . . | . . @ |
| @ . . | . Y . | . . @ |
| . . Y | . . . | Y . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . x | x . x | x . . |
| Y x . | . . . | . x Y |
+-------+-------+-------+
| . . . | x . x | . . . |
| . x . | . . . | . x . |
| . x . | . x . | . x . |
+-------+-------+-------+
So i tried to add 2 UA digits (i just took the first 2 in the c28 cells different to those in the Y cells) and solve it in a first step. It is sufficient to find a single solution then to know, that the puzzle has multiple solutions. This happened for about 25 % of the puzzles.
Though this way i had 75 % more solver calls, the search was 4.5 % faster.
Now this will not help us much for the symm. 18 clue search, and maybe this trick is already used in some solvers (for low clue puzzles).
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: Symmetric 18s
by Serg » Sun Apr 22, 2012 6:51 am
Hi, colleagues!
I've just filtered last eleven's list of patterns by applying 3 additional composition rules. Here is my program report.
New number of "rectified" patterns - 192125. So, I was succeeded in going beyond 200000 patterns. 32424 patterns were filtered out. It seems to be ultimate considering already published composition rules.
I'll comment this result ASAP.
Zipped file can be loaded here .
Serg
I've just filtered last eleven's list of patterns by applying 3 additional composition rules. Here is my program report.
- Code: Select all
Composition rules filter (12 rules), version 1.1
Total number of processed patterns: 224549
Filtering statistics
2 empty rows (columns) in a band (stack): ...........filtered out 0 patterns
Composition rule 1: .................................filtered out 0 patterns
Composition rule 2: .................................filtered out 0 patterns
Composition rule 3: .................................filtered out 0 patterns
Composition rule 4: .................................filtered out 0 patterns
Composition rule 5: .................................filtered out 0 patterns
Composition rule 6: .................................filtered out 0 patterns
Composition rule 7: .................................filtered out 0 patterns
Composition rule 8: .................................filtered out 0 patterns
Patterns having 9 clues in a box: ...................filtered out 36 patterns
One-band-free patterns with 4/5-clues in corner box: filtered out 17838 patterns
Subsets of Magic Pattern: ...........................filtered out 14550 patterns
Totally filtered out patterns: 32424
Valid patterns: .............. 192125
Total program execution time: 5 seconds
New number of "rectified" patterns - 192125. So, I was succeeded in going beyond 200000 patterns. 32424 patterns were filtered out. It seems to be ultimate considering already published composition rules.
I'll comment this result ASAP.
Zipped file can be loaded here .
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: Symmetric 18s
by Serg » Sun Apr 22, 2012 8:27 pm
Hi, all!
The first additional composition rule is trivial:
I added this rule for the sake of completeness (and to cross-check eleven's results) to my filter and got no additional filtered out patterns, as it was expected.
The next additional rule was discussed in my previous post.
The next rule is provided by my favorite Magic Pattern (see thread How to prove non-existance of 8-clue valid puzzles?).
Let me rearrange it to more convinient form:
udosuk was the first who invented it in 2007. Red Ed proved this pattern has no valid puzzles (see thread Ask for some patterns that they don't have puzzles).
Composition rule 3 is based on Magic Pattern. But rule 3 uses not entire potential of Magic Pattern. It turns out that Magic Pattern itself can exclude 14000 patterns (after applying composition rules 1-9).
Well, I have remaining rather strange idea that cannot be called as "composition rule".
Let's consider a pattern having 9 clues in the central box and N clues outside that box (this is exactly a pattern from coloin's patterns' family "9plusN"). Let's define similar patterns for such patterns. Similar pattern has 8 clues (instead of 9) in the central box and N+1 clues outside this box, provided that its N outside clues coincides with N clues of the given pattern (but 1 clue differs from the given pattern). Note that both patterns have N+9 clues in total.
Asume that given "9plusN" pattern has valid puzzles. Then similar pattern must have valid puzzles too, because remaining 9-th clue in the central box is uniquely determined and 1 extra clue outside central box doesn't destroy puzzle's solution. So, we don't need to consider patterns having 9 clues in a box, because we'll consider similar patterns having 8 clues in a box. If such "similar" pattern will have valid puzzles, we can find proper "9plusN" patterns also having valid puzzles by minimality analisys - we should check all N+1 outside clues of the valid puzzle found - are all such clues necessary for that puzzle having unique solution. If one of the N+1 clues is extra clue - we can easily get "9plusN" valid puzzle (and hence "9plusN" pattern having valid puzzles). If all "similar" 8plusN+1 valid puzzles are minimal, there must not exist "9plusN" valid puzzles.
So, we can ignore patterns having 9 clues in a box. I implemented this rule in my filter, but it turns out that there are 36 such patterns only.
I exhausted previously found investigations' results and "hot" ideas. So, I need time to find some new ideas.
Serg
The first additional composition rule is trivial:
- Code: Select all
Rule 9. Pattern has no valid puzzles if its band (stack) contains 2 empty rows (columns).
I added this rule for the sake of completeness (and to cross-check eleven's results) to my filter and got no additional filtered out patterns, as it was expected.
The next additional rule was discussed in my previous post.
- Code: Select all
Rule 10. Pattern has no valid puzzles if it is subset of the pattern posted below
+-----+-----+-----+
|x . .|. . .|. . .|
|x . .|. . .|. . .|
|x x x|. . .|. . .|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|x x x|x x x|x x x|
|x x x|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
The next rule is provided by my favorite Magic Pattern (see thread How to prove non-existance of 8-clue valid puzzles?).
- 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
Let me rearrange it to more convinient form:
- 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
udosuk was the first who invented it in 2007. Red Ed proved this pattern has no valid puzzles (see thread Ask for some patterns that they don't have puzzles).
Composition rule 3 is based on Magic Pattern. But rule 3 uses not entire potential of Magic Pattern. It turns out that Magic Pattern itself can exclude 14000 patterns (after applying composition rules 1-9).
- Code: Select all
Rule 11. Pattern has no valid puzzles if it is subset of the pattern posted below
+-----+-----+-----+
|. . .|. . x|. . x|
|. . .|. . x|. . x|
|. . x|. . x|. . x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
Well, I have remaining rather strange idea that cannot be called as "composition rule".
Let's consider a pattern having 9 clues in the central box and N clues outside that box (this is exactly a pattern from coloin's patterns' family "9plusN"). Let's define similar patterns for such patterns. Similar pattern has 8 clues (instead of 9) in the central box and N+1 clues outside this box, provided that its N outside clues coincides with N clues of the given pattern (but 1 clue differs from the given pattern). Note that both patterns have N+9 clues in total.
Asume that given "9plusN" pattern has valid puzzles. Then similar pattern must have valid puzzles too, because remaining 9-th clue in the central box is uniquely determined and 1 extra clue outside central box doesn't destroy puzzle's solution. So, we don't need to consider patterns having 9 clues in a box, because we'll consider similar patterns having 8 clues in a box. If such "similar" pattern will have valid puzzles, we can find proper "9plusN" patterns also having valid puzzles by minimality analisys - we should check all N+1 outside clues of the valid puzzle found - are all such clues necessary for that puzzle having unique solution. If one of the N+1 clues is extra clue - we can easily get "9plusN" valid puzzle (and hence "9plusN" pattern having valid puzzles). If all "similar" 8plusN+1 valid puzzles are minimal, there must not exist "9plusN" valid puzzles.
So, we can ignore patterns having 9 clues in a box. I implemented this rule in my filter, but it turns out that there are 36 such patterns only.
I exhausted previously found investigations' results and "hot" ideas. So, I need time to find some new ideas.
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: Symmetric 18s
by coloin » Sun Apr 22, 2012 10:33 pm
Hi Serg
How many patterns would be excluded which have 6 clues in the central box ?
Got to say at this point that there are no symetrical 9plus12s in my list.
But not proven just yet. Might be worth excluding for now ?
The most clues that are present in the central box in known symmetric 18s is 4. So it might be provisionally and tentativly worth excluding those with 5 clues in box 5 as well !
I did try to search a symmetrical 9plus15 pattern. There were a lot of puzzles - i eventually got one where i was able to remove 6 clues - leaving 3. However it wasnt quite symmetrical.
However it did have the advantage that I was searching for several box 5 patterns at the same time.
C
How many patterns would be excluded which have 6 clues in the central box ?
Got to say at this point that there are no symetrical 9plus12s in my list.
But not proven just yet. Might be worth excluding for now ?
The most clues that are present in the central box in known symmetric 18s is 4. So it might be provisionally and tentativly worth excluding those with 5 clues in box 5 as well !
I did try to search a symmetrical 9plus15 pattern. There were a lot of puzzles - i eventually got one where i was able to remove 6 clues - leaving 3. However it wasnt quite symmetrical.
- Code: Select all
+---+---+---+
|...|.1.|...|
|..2|...|7..|
|..7|...|3..|
+---+---+---+
|.6.|543|.1.|
|2..|681|..9|
|...|927|...|
+---+---+---+
|...|...|...|
|14.|...|.96|
|...|3.2|...|
+---+---+---+
+---+---+---+
|...|.1.|...|
|..2|...|7..|
|..7|...|3..|
+---+---+---+
|.6.|54.|.1.|
|2..|...|..9|
|...|..7|...|
+---+---+---+
|...|...|...|
|14.|...|.96|
|...|3.2|...|
+---+---+---+ not quite
However it did have the advantage that I was searching for several box 5 patterns at the same time.
C
- coloin
- Posts: 2494
- Joined: 05 May 2005
- Location: Devon
Re: Symmetric 18s
by eleven » Tue Apr 24, 2012 10:56 am
After Serg's filterings and the tests by afmob and myself, unfortunately little has changed to my estimate, what effort would be needed for an exhaustive search for all vertical (or horizontal) symmetric 18 clue puzzles. I still expect, that about 1 mio core hours would be needed.
This is the distribution of the number of morphs for the remaining patterns:
I made extra files sym18patsm4.txt to sym18patsm768.txt and zipped them there. [Edit: Now they are sorted also.]
This is the distribution of the number of morphs for the remaining patterns:
- Code: Select all
4 79220
8 75149
12 200
16 24795
24 2870
32 6214
48 1515
64 1406
72 4
96 425
128 176
144 11
192 110
256 7
288 8
384 12
576 2
768 1
I made extra files sym18patsm4.txt to sym18patsm768.txt and zipped them there. [Edit: Now they are sorted also.]
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: Symmetric 18s
by Serg » Tue Apr 24, 2012 3:04 pm
Hi, eleven!
Do you mean your exhaustive search program needs 5 hours of CPU time per pattern? (What is estimated average CPU time per pattern?)
Serg
eleven wrote:After Serg's filterings and the tests by afmob and myself, unfortunately little has changed to my estimate, what effort would be needed for an exhaustive search for all vertical (or horizontal) symmetric 18 clue puzzles. I still expect, that about 1 mio core hours would be needed.
Do you mean your exhaustive search program needs 5 hours of CPU time per pattern? (What is estimated average CPU time per pattern?)
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: Symmetric 18s
by eleven » Tue Apr 24, 2012 6:52 pm
Serg wrote:Do you mean your exhaustive search program needs 5 hours of CPU time per pattern? (What is estimated average CPU time per pattern?)
The main time is used for solving the puzzles. I had tried the first 9 patterns with 4 morphs, which have valid sudokus. On average i had to solve 1.7 bio puzzles and it took about 10 hours per pattern.
I also tried 5 patterns with 8 or 16 morphs, with more than 3 hours on average.
And i noticed, that the number of puzzles seems to increase for later patterns in the list (since the cells are better distributed then).
If you want a more exact estimate, i simply could count the puzzles in all patterns without solving it (i make the last equivalence check with 14 clues, after that probably the time needed for the check is longer than for solving the remaining non equivalent puzzles). But this takes about 2.5 minutes for a pattern with 1.5 bio puzzles, i.e. some days for the list. I cant do that now, maybe in a week.
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: Symmetric 18s
by Serg » Tue Apr 24, 2012 9:46 pm
Hi, eleven!
I have exhaustive searching method which takes about 5 minutes per pattern. I used it during investigations of one-clue-boxes patterns. The main problem with this method is to account for possible automorhpisms correctly. So, I was forced to analyse (manually) possible intermediate search configurations before coding appropriate program. It took me about month per search (separate search was performed for given map, i.e. 10-40 patterns collection). I am trying now to write a program, which will be able to analyse a pattern (a map) automatically. I hope I'll succeed in doing it.
Serg
I have exhaustive searching method which takes about 5 minutes per pattern. I used it during investigations of one-clue-boxes patterns. The main problem with this method is to account for possible automorhpisms correctly. So, I was forced to analyse (manually) possible intermediate search configurations before coding appropriate program. It took me about month per search (separate search was performed for given map, i.e. 10-40 patterns collection). I am trying now to write a program, which will be able to analyse a pattern (a map) automatically. I hope I'll succeed in doing it.
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
by Afmob » Wed Apr 25, 2012 6:19 am
I don't think that we should filter out patterns with 9 clues in a box, row or column for the following reasons:
- They are only few patterns with this property, so this doesn't reduce the search space significantly.
- With one box, row or column fixed, they have at most 9^9/4 essentially different puzzles which is quite an overestimation since it assumes that the clues don't see each other.
- Those similar patterns you talk of might not necessarily be symmetric.
- We should only filter out pattern where we know that they don't have valid puzzles. As far as I know, we didn't assume minimality.
Furthermore, I would like to see some validation of your composition rules 4-8.
- They are only few patterns with this property, so this doesn't reduce the search space significantly.
- With one box, row or column fixed, they have at most 9^9/4 essentially different puzzles which is quite an overestimation since it assumes that the clues don't see each other.
- Those similar patterns you talk of might not necessarily be symmetric.
- We should only filter out pattern where we know that they don't have valid puzzles. As far as I know, we didn't assume minimality.
Furthermore, I would like to see some validation of your composition rules 4-8.
- Afmob
- Posts: 132
- Joined: 28 June 2011
Re: Symmetric 18s
by coloin » Wed Apr 25, 2012 7:13 pm
Well I think we perhaps will soon be able to show that there are no symmetric 18s with 6 clues in a column or box.
the paucity of 9plus12s [box] means that it is very unlikely and none of the found ones are symmetrical. Probably there will be a symmetrical 9 plus13.[box]
With a full column [or row] the minumum extra clues needed looks like 12 also. [not looked too hard though]
Here is a 9plus12[column] found from a 17.
It also has implications for all patterns if both are proven
- minimum of 12 clues in B12346789
- minimum of 12 clues in 8 out of the 9 rows or columns.
would be an example of symmetric 18 pattern when 6 out of the 9 clues in a column are given clues
With a vertical 9 - the essential 2 clues in r1c46 means there will not be many patterns with 6 clues in c5.
The number of possible patterns is small with a horizontal 6/9plus12.
C
the paucity of 9plus12s [box] means that it is very unlikely and none of the found ones are symmetrical. Probably there will be a symmetrical 9 plus13.[box]
With a full column [or row] the minumum extra clues needed looks like 12 also. [not looked too hard though]
Here is a 9plus12[column] found from a 17.
- Code: Select all
+---+---+---+
|...|51.|..8|
|4..|.2.|...|
|9..|.3.|...|
+---+---+---+
|...|.4.|97.|
|.82|.5.|...|
|...|.6.|3..|
+---+---+---+
|...|.73|.9.|
|.5.|.8.|...|
|...|.9.|...|
+---+---+---+ another 9plus12
+---+---+---+
|...|51.|..8|
|4..|.2.|...|
|9..|...|...|
+---+---+---+
|...|.4.|97.|
|.82|.5.|...|
|...|...|3..|
+---+---+---+
|...|..3|.9.|
|.5.|.8.|...|
|...|...|...|
+---+---+---+ from a 17
It also has implications for all patterns if both are proven
- minimum of 12 clues in B12346789
- minimum of 12 clues in 8 out of the 9 rows or columns.
- Code: Select all
+---+---+---+
|...|xxx|...|
|x..|.x.|..x|
|x..|.x.|..x|
+---+---+---+
|...|.x.|...|
|.x.|.x.|.x.|
|...|.x.|...|
+---+---+---+
|...|.x.|...|
|.xx|.x.|xx.|
|...|.x.|...|
+---+---+---+
would be an example of symmetric 18 pattern when 6 out of the 9 clues in a column are given clues
With a vertical 9 - the essential 2 clues in r1c46 means there will not be many patterns with 6 clues in c5.
The number of possible patterns is small with a horizontal 6/9plus12.
C
- coloin
- Posts: 2494
- Joined: 05 May 2005
- Location: Devon
Re: Symmetric 18s
by eleven » Wed Apr 25, 2012 10:02 pm
Serg wrote:Hi, eleven!
I have exhaustive searching method which takes about 5 minutes per pattern. I used it during investigations of one-clue-boxes patterns. The main problem with this method is to account for possible automorhpisms correctly.
Wow, great. I guess i got the idea. Hope that i can try it soon, maybe at the weekend.
To use the automorphisms should not be a big problem, if the possible band completions are calculated individually for each pattern.
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: Symmetric 18s
by Serg » Wed Apr 25, 2012 11:04 pm
Hi, coloin!
Please, wait some time. I am now cross-checking our results. I am planning to calculate the power of "9plus11 don't exist" rule (to calculate - how many patterns can be excluded if this rule can be proved) just after cross-checking.
I think some kind of proof (or result of exhaustive search) must be presented.
Any kind of proof is necessary.
Serg
coloin wrote:How many patterns would be excluded which have 6 clues in the central box ?
Please, wait some time. I am now cross-checking our results. I am planning to calculate the power of "9plus11 don't exist" rule (to calculate - how many patterns can be excluded if this rule can be proved) just after cross-checking.
coloin wrote:Got to say at this point that there are no symetrical 9plus12s in my list.
But not proven just yet. Might be worth excluding for now ?
I think some kind of proof (or result of exhaustive search) must be presented.
coloin wrote:The most clues that are present in the central box in known symmetric 18s is 4. So it might be provisionally and tentativly worth excluding those with 5 clues in box 5 as well !
Any kind of proof is necessary.
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
