Symmetric 18s

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

Re: Symmetric 18s

Postby eleven » Fri Apr 20, 2012 9:59 am

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.
eleven
 
Posts: 1564
Joined: 10 February 2008

Postby 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: 130
Joined: 28 June 2011

Re:

Postby Serg » Fri Apr 20, 2012 10:40 am

Hello, Afmob!
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
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

UA vs digit guesses

Postby 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 @.
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: 1564
Joined: 10 February 2008

Re: Symmetric 18s

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

Re: Symmetric 18s

Postby Serg » Sun Apr 22, 2012 8:27 pm

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

Re: Symmetric 18s

Postby 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.
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: 1637
Joined: 05 May 2005

Re: Symmetric 18s

Postby 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:
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: 1564
Joined: 10 February 2008

Re: Symmetric 18s

Postby Serg » Tue Apr 24, 2012 3:04 pm

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

Re: Symmetric 18s

Postby 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: 1564
Joined: 10 February 2008

Re: Symmetric 18s

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

Postby 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.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby 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.
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: 1637
Joined: 05 May 2005

Re: Symmetric 18s

Postby 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: 1564
Joined: 10 February 2008

Re: Symmetric 18s

Postby Serg » Wed Apr 25, 2012 11:04 pm

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

PreviousNext

Return to General