## Symmetric 18s

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

### Re:

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

Well, I agree that it is not so much sense in filtering out patterns with 9 clues in a box. Though I think your points about symmetry of "similar" patterns and about minimality are not quite true, but it is not worth spending time for discussion concerning these questions. If you like I could repeat filtering without rejecting patterns having 9 clues in a box.
Afmob wrote:Furthermore, I would like to see some validation of your composition rules 4-8.

All these rules were validated by exhaustive search done by my program. (But I haven't seen any independent confirmation of these results.)

Rules 4-7 were introduced in the thread How to prove non-existance of 8-clue valid puzzles?. Rule 8 was introduced in the thread One-clue-boxes patterns.

Serg
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

Hi, eleven!
I've found a bug in my filter (I was too fast with my results) . Some patterns were filtered out wrongly, but others were not filtered though they should be filtered. I suppose the error concerns several percents of patterns only. It seems correct number of "rectified" patterns will be less (about 188000 patterns).

Could you upload your initial file containing patterns (300000 patterns), but without isomorph. duplicates?

Serg
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

Here you are. With my tools its not trivial to eliminate the duplicates too, but i am quite confident, that i removed the ones with higher minlex form
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

Hi, colleagues!
I fixed a bug in my filter and filtered last eleven's list of patterns (file "sym18patterns_n-e.txt" w/o isomorph. duplicates). (I canceled filtering rule for patterns having 9 clues in a box at the request of Afmob.)
Here is my program's report.
Code: Select all
`Composition rules filter (11 rules), version 1.3Total number of processed patterns: 294313Filtering statistics2 empty rows (columns) in a band (stack): ...........filtered out      0 patterns (Rule 9)Composition rule 1: .................................filtered out   6087 patternsComposition rule 2: .................................filtered out  47491 patternsComposition rule 3: .................................filtered out    375 patternsComposition rule 4: .................................filtered out      0 patternsComposition rule 5: .................................filtered out      0 patternsComposition rule 6: .................................filtered out    342 patternsComposition rule 7: .................................filtered out      0 patternsComposition rule 8: .................................filtered out   3906 patternsOne-band-free patterns with 4/5-clues in corner box: filtered out  22281 patterns (Rule 10)Subsets of Magic Pattern: ...........................filtered out  14684 patterns (Rule 11)Totally filtered out patterns:  95166Valid patterns: .............. 199147Total program execution time: 11 seconds`

New number of "rectified" patterns - 199147. 95166 patterns were filtered out.

I've tested coloin's suggestions (new "composition rules" candidates):
coloin wrote:Unless it can be optimised furthur.......suggestions anyone ?
Proof 1
Concerning clues in the horzontal 27 clue bands : Proof that a valid 3,4,27 or 2,5,27 doesnt exist.
Therefore in a 17-puzzle there can never be more than 9 clues in a single band and always at least 8 in two of the three bands.

Proof 2
Concerning clues in Boxes - with a full Box 5 : Proof that a valid 9plus11 doesnt exist. Therefore there must always be 12 or more clues in 8 of the boxes [~B12346789].
Or better still - prove that we have found all the valid 9plus12 puzzles. Therefore we have found all the 5plus12 puzzles [? 6] , therefore new 17 puzzles have a maximum of 4 clues in a box.

If we could prove the first coloin's rule "Each valid pattern must have at least 8 clues in two of the three bands (stacks)", we could filter out 7333 patterns from the last version of possible symmetric 18-clue patterns (published in this post). But in what way this rule can be proved?

The second coloin's rule "Sum of the clues in any 8 boxes of valid pattern must not be less than 12" can filter out 2869 patterns. (I hoped for the better...) This rule must be proved too.

Serg

[Edited. I fixed a bug in my filtering program and posted new program running statistics (number of filtered out patterns, etc.). New resulting file with rectified patterns is available by the link posted above. Thanks to Afmob who found an error in my resulting data.]
Last edited by Serg on Thu Apr 11, 2013 8:39 am, edited 1 time in total.
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

Hi, people!
I propose to classify 18-clue symmetric patterns by their ordered distributions of clues over boxes or simply "distributions". For example, 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|+-----+-----+-----+`

has distribution 005999999 (each digit represents number of clues in some box; list must be sorted).

All distributions for 188268 possible valid patterns from the last version of eleven's list (see link for downloading in my previous post) are published below.
Code: Select all
`18-clue possible symmetric distributions (eleven's list)  N Distribution Patterns--------------------------  1  000022338     21  2  000022446     96  3  000022455     32  4  000033336    110  5  000033444     93  6  000122229     20  7  000122337    102  8  000122445    156  9  000133335    308 10  000222228     44 11  000222237    140 12  000222246    335 13  000222255    174 14  000222336    312 15  000222444    156 16  000223335    334 17  000223344    199 18  000233334    313 19  001111338     24 20  001111446    117 21  001111455     39 22  001112229     23 23  001112238     43 24  001112247    162 25  001112256    297 26  001112337    242 27  001112445    390 28  001113336    603 29  001113345    798 30  001113444    319 31  001122228    103 32  001122237    340 33  001122246    894 34  001122255    464 35  001122336   1689 36  001122345   1230 37  001122444    911 38  001123335    976 39  001123344    637 40  001133334    797 41  001222227    254 42  001222236    609 43  001222245    756 44  001222335   1246 45  001223334   1000 46  002222226    696 47  002222235    888 48  002222244    551 49  002222334   1610 50  011111229      9 51  011111337    116 52  011111355    129 53  011111445    301 54  011112228     54 55  011112237    180 56  011112246    378 57  011112255    349 58  011112336    522 59  011112444    903 60  011113335   1015 61  011113344   1286 62  011122227    356 63  011122335   3539 64  011122344   2573 65  011133333   2496 66  011222226   1350 67  011222235   2587 68  011222244   3512 69  011222334   8629   observed:  1 70  011223333   6865 71  012222225   1454 72  012222333   6584 73  022222224   3158   observed:  2 74  022222233   5937   observed:  1 75  111111228     44 76  111111336    414 77  111111444    756 78  111112227    592 79  111112236   1550 80  111112245   2485 81  111112335   3215 82  111112344   3112 83  111113334   5335 84  111122226   2378 85  111122235   4990 86  111122244   4782 87  111122334  15285   observed:  4 88  111123333   5663   observed:  1 89  111222225   6077 90  111222234   9976   observed:  2 91  111222333  12008   observed: 32 92  112222224   9653   observed:  3 93  112222233  15826   observed: 34 94  122222223   6632   observed: 24 95  222222222   1560   observed: 12Total number of different distributions  :     95Total number of patterns in eleven's list: 188268Total number of observed patterns        :    116`

So, this is my idea of classification - I propose to divide overall exhaustive search to separate small procedures of searching through alone distributions. Therefore overall search can be parallelised and we can see intermediate results of searching (for example, 352 patterns only should be searched through to prove that there are no valid symmetric 18-clue puzzles having 4 empty boxes).

It is worth noting that there exist 251 distributions for 18-clue puzzles (valid or invalid, symmetric or asymmetric).

Serg

[Edited: I updated number of observed patterns - 108 sym. essentially different patterns are known now (02.06.2012).]
[Edited: I updated number of observed patterns - 109 sym. essentially different patterns are known now (03.06.2012). Number of observed patterns for distribution 111222333 was updated.]
[Edited: I updated number of observed patterns - 110 sym. essentially different patterns are known now (04.06.2012). Number of observed patterns for distribution 122222223 was updated.]
[Edited: I updated number of observed patterns - 112 sym. essentially different patterns are known now (24.06.2012). Number of observed patterns for distributions 122222223 and 222222222 were updated (#111 has 222222222 distr., #112 has 122222223 distr.).]
[Updated number of observed patterns - 113 sym. essentially different patterns are known now (28.06.2012). Pattern #113 has new distribution: 011222334.]
[Updated number of observed patterns - 114 sym. essentially different patterns are known now (9.07.2012). Pattern #114 has distribution: 112222233.]
[Updated number of observed patterns - 115 sym. essentially different patterns are known now (23.07.2012). Pattern #115 has distribution: 112222233.]
[Updated number of observed patterns - 116 sym. essentially different patterns are known now (10.08.2012). Pattern #116 has new distribution: 111123333.]
Last edited by Serg on Sat Aug 11, 2012 6:59 am, edited 8 times in total.
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

eleven wrote:I guess i got the idea.

Obviously i did not
It also would take hours to search an average pattern.
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

Just to say, what i had in mind. Maybe it is similar to Serg's idea.

The first step was to look for a given band pattern, how many e-d band solutions there are.
I tested it for this one, and it did not look bad.
Code: Select all
` +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . 1 . | . . . | | . . 1 | . . . | 1 . . | +-------+-------+-------+`

Out of 653184 possible solutions only 1240 fixed all UA's.
(The first drawback was, that for another example with 6 cells i got more than 100000.)

Now the task would be to assign the other 15 cells in a way, that they have a unique solution with one of the 1240 bands. But this soon turned out to take too long for all of them (note, that you cant minlex them, and you cant use the 2 automorphisms, because both is fixed by the band solutions).

The next try was, to combine them with all possible solutions of the middle stack. For the test I again took the stack from the first pattern, which is known to have a valid puzzle.
Here i got 343632 from 2612736 possible completions with all UA's fixed (no automorphisms to use).

It took 2 hours to go through all combinations and check the UA's, in the hope, that only a few would pass the check. But i ended up with 307090 non equivalent ones.
Here is the first.
Code: Select all
` +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . x . | . . . | | . . x | . . . | x . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . x | x . x | x . . | | x x . | . . . | . x x | +-------+-------+-------+ | . . . | x . x | . . . | | . x . | . . . | . x . | | . x . | . x . | . x . | +-------+-------+-------+ +-------+-------+-------+ | 2 4 6 | 8 1 9 | 7 5 3 | | 5 8 7 | 6 3 2 | 9 1 4 | | 9 3 1 | 7 5 4 | 2 8 6 | +-------+-------+-------+ | . . . | 9 8 3 | . . . | | . . x | 1 4 6 | x . . | | x x . | 5 2 7 | . x x | +-------+-------+-------+ | . . . | 3 9 5 | . . . | | . x . | 4 6 8 | . x . | | . x . | 2 7 1 | . x . | +-------+-------+-------+`

Now the task would be to assign the 10 cells marked x in a way, that together with the fixed pattern cells, they lead to a unique solution, which matches the other numbers. This does not look hard, but it will take some time (i did not try), too long for all of them.
So it does not help very much, that those partial solutions could be used for 228 patterns in the list.
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

Hi, eleven!
You are right, I am using searching method very similar to the method described by you. I've already pushed this idea to the working method (as you know, my methods' description was published in the thread One-clue-boxes patterns).

You chose rather complicated pattern for analysis (I successfully investigated less complicated ones). But I hope I'll be able to process such patterns in some time.

Serg
Serg
2018 Supporter

Posts: 607
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

Serg wrote:You chose rather complicated pattern for analysis.

Unfortunately not. The really complicated ones are at the end of the list with 6 clues in each band and stack.
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

All known (vertical) symmetric puzzles (389 with 107 patterns) are in a single cluster with hamming distance 8, i.e. starting with one of them you can find all others with {-4+4}.
This is surprising for me, because to my knowledge only i used neighbourhood search to find them (Ano1 had used it to find the 18 clues, but his symmetric ones come from a huge set of more than 1 bio puzzles).

So it's not unprobable for me, that at least a full {-5+5} search could be enough to find all existing puzzles - but we could never be sure without an exhaustive search.
However, with my current program a {-5+5} takes about 2 days for one puzzle.
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

eleven wrote:... hamming distance 8, i.e. starting with one of them you can find all others with {-4+4}.

Oops, this is not true. For the hamming distance a number change in a fixed cell only counts one. But for {-m+n} you would have to remove the cell and add it again with the other number.
So e.g. you need a {-1+1} for hamming distance 1 and either a {-1+1} (if the cell changes) or a {-2+2} (if there are 2 fixed cells with changed number) for hamming distance 2.
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

Code: Select all
` +-------+-------+-------+ | . . . | . 1 . | . . . | | . . 2 | . . . | 3 . . | | . . 4 | . 5 . | 6 . . | +-------+-------+-------+ | . . . | 6 . 3 | . . . | | . . 6 | . . . | 2 . . | | . 7 . | . . . | . 8 . | +-------+-------+-------+ | . . . | 4 . 2 | . . . | | . 9 . | . . . | . 1 . | | 5 . . | . . . | . . 7 | +-------+-------+-------+....1......2...3....4.5.6.....6.3.....6...2...7.....8....4.2....9.....1.5.......7 #108 eleven`

The magic number is reached, 108=2*2*3*3*3 patterns for 18=2*3*3 clue puzzles with 2 automorphisms.
My board is full - and i hope, no one will ever find another pattern
http://imageshack.us/photo/my-images/4/vs18108.jpg/
eleven

Posts: 1866
Joined: 10 February 2008

### Re: Symmetric 18s

Very good. Maybe you wont find another !

Serg wrote:95 222222222 1560 observed: 10
95 222222222 1560 observed: 11

perhaps we could have the 1560 patterns !

it would be easy to generate 222222222-18s
It would be easy to minlex their pattern

Is this how you found this 18 ?

BTW do you know the command to use gsf's program to filter 222222222-18s ? Can be combined with a {-2+2}

C
coloin

Posts: 1734
Joined: 05 May 2005

### Re: Symmetric 18s

eleven, good show on the 108th symmetric 18!

On your earlier comment, {-4+4} does produce max Hamming distance = 8, but knowing max Hamming dist = 8 might require {-8+8} worst case, to generate all from one. Was that the gist of your statement?
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: Symmetric 18s

Thanks.
coloin wrote:Is this how you found this 18 ?

No, i made {-5+5} on known puzzles.

ronk wrote:On your earlier comment, {-4+4} does produce max Hamming distance = 8, but knowing max Hamming dist = 8 might require {-8+8} worst case, to generate all from one. Was that the gist of your statement?

Yes. I dont know a tool, which quickly checks, if 2 puzzles are within {-n+n} (i used gsf's for the hamming distance). I guess, that {-5+5} could be enough for the known ones, but not {-4+4}.
eleven

Posts: 1866
Joined: 10 February 2008

PreviousNext