The New Sudoku Players' Forum

[Serg]

Hi, Afmob!

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.

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]

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

[eleven]

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

[Serg]

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.3

Total number of processed patterns: 294313

Filtering statistics

2 empty rows (columns) in a band (stack): ...........filtered out      0 patterns (Rule 9)
Composition rule 1: .................................filtered out   6087 patterns
Composition rule 2: .................................filtered out  47491 patterns
Composition rule 3: .................................filtered out    375 patterns
Composition rule 4: .................................filtered out      0 patterns
Composition rule 5: .................................filtered out      0 patterns
Composition rule 6: .................................filtered out    342 patterns
Composition rule 7: .................................filtered out      0 patterns
Composition rule 8: .................................filtered out   3906 patterns
One-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:  95166
Valid patterns: .............. 199147

Total program execution time: 11 seconds


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

Zipped file can be downloaded here .

I've tested coloin's suggestions (new "composition rules" candidates):

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.]

[Serg]

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: 12

Total number of different distributions  :     95
Total number of patterns in eleven's list: 188268
Total 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.]

[eleven]

I guess i got the idea.

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

[eleven]

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.

[Serg]

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

[eleven]

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]

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]

... 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]

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/

[coloin]

Very good. Maybe you wont find another !

95 222222222 1560 observed: 10
will now read
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

[ronk]

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?

[eleven]

Thanks.

Is this how you found this 18 ?

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

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}.