## Symmetric 18s

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

### Re: Symmetric 18s

Hi, coloin!
coloin wrote:Hi, remind me again how you check a pattern ?
if a pattern is a potential puzzle
if all the empty spaces in a potential puzzle are pattern-i
Do you ?
generate all possible ED ways to fill the empty clue pattern [pattern-i]
generate a token grid completion for the pattern-i
show that each token pattern generated has > 1 sol ?
I don't understand, what are "pattern-i" and "token" grid/pattern.

I generate all possible e-d ways of a band and a stack empty cells fillings (band and stack are analyzed separately), then I filtered out fillings having unhitted UA sets. Then rectified (hence not containing unhitted UA sets) band and stack configurations are combined and checked for unhitted UA sets. If band/stack combination contains no unhitted UA sets, we can be sure this combination produces valid puzzle. That valid puzzle can be found by completing band/stack combination - completion will be the puzzle.

Basically this method has already been described. New point is to fill empty cells only, not all band/stack cells. This approach dramatically speeds up searching through high-clue patterns.

Serg
Serg
2018 Supporter

Posts: 608
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

the pattern is
Code: Select all
`+---+---+---+|xxx|xxx|xxx||...|.x.|...||...|.x.|...|+---+---+---+|xxx|.x.|xxx||xxx|.x.|xxx||xxx|.x.|xxx|+---+---+---+|xxx|.x.|xxx||xxx|.x.|xxx||xxx|.x.|xxx|+---+---+---+ `

the reciprocal is pattern-i [the empty cells]
here is an example
Code: Select all
`+---+---+---+|...|...|...||123|4.6|789||746|3.8|125|+---+---+---+|...|7.2|...||...|9.1|...||...|5.4|...|+---+---+---+|...|1.3|...||...|8.9|...||...|6.5|...|+---+---+---+`

i see - essentially you look for UA in the empty cells ... [by definition they are unhit]

do this by adding in any valid numbers to give a 81-clue token grid solution
remove all pattern-i clues from the grid solution and test the remaining cells for uniquness [no UA in the pattern-i]

however with this pattern-i, i have easily got > 58000 Ed pattern-i [ rather more than i guessed though !] and this wont be exhaustive.
but testing the resulting grids for 1 sol is very quick

Serg wrote: New point is to fill empty cells only, not all band/stack cells. This approach dramatically speeds up searching through high-clue patterns.
..... so an improvement then !!

C
coloin

Posts: 1738
Joined: 05 May 2005

### Re: Symmetric 18s

Hi, coloin!
coloin wrote:do this by adding in any valid numbers to give a 81-clue token grid solution
remove all pattern-i clues from the grid solution and test the remaining cells for uniquness [no UA in the pattern-i]
Yes, I check "pattern-i" for unhitted UAs exactly according to your description - I treat completion of "pattern-i" (i.e. collection of cells not containing clues which were filled by numbers) as puzzle and check - has this puzzle unique solution? If it has unique solution, we can be sure "pattern-i" doesn't contain unhitted UAs.
coloin wrote:however with this pattern-i, i have easily got > 58000 Ed pattern-i [ rather more than i guessed though !] and this wont be exhaustive.
but testing the resulting grids for 1 sol is very quick
Key consideration - it is enough to use only one completion of "pattern-i" to check "pattern-i" for unhitted UAs. (I borrowed this idea from blue.)

Serg
Serg
2018 Supporter

Posts: 608
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

If I might make a small observation, I made a quick run and discovered that the number of solutions was always

2, 4, or 8

or

3

or their multiples, 6, 12 or 24.

This suggests that a proof is possible the the pattern always has at least one UA4 or one UA6. Maybe that could be proven analytically? A diagonally symmetric morph that might help is
Code: Select all
` X X X X X X X 0 0 X X X X X X X 0 0 X X X X X X X 0 0 X X X X X X X 0 0 X X X X X X X 0 0 X X X X X X X 0 0 X X X X X X X X X 0 0 0 0 0 0 X 0 0  0 0 0 0 0 0 X 0 0 `

Regards,

Mike

m_b_metcalf
2017 Supporter

Posts: 9395
Joined: 15 May 2006
Location: Berlin

### Re: Symmetric 18s

Another small observation is that the pattern-i generates the remaining clues in box2
Code: Select all
`+---+---+---+|...|...|...||123|4.6|789||746|3.8|125|+---+---+---+|...|7.2|...||...|9.1|...||...|5.4|...|+---+---+---+|...|1.3|...||...|8.9|...||...|6.5|...|+---+---+---+`

Code: Select all
`+---+---+---+|...|217|...||123|456|789||746|398|125|+---+---+---+|...|7.2|...||...|9.1|...||...|5.4|...|+---+---+---+|...|1.3|...||...|8.9|...||...|6.5|...|+---+---+---+ `

but i cant extend this to a proof of our original pattern ....
C
coloin

Posts: 1738
Joined: 05 May 2005

### Re: Symmetric 18s

m_b_metcalf wrote:...This suggests that a proof is possible the the pattern always has at least one UA4 or one UA6.

There are 12 different two-row UA.
Four of them are UA18 and therefore are out of scope of this pattern, but I can't see any reason why any of the others UA of size 4, 6, 8 and 12 not to participate in the non-givens. In addition the non-givens from outside the 2-rows could result in larger UA.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: Symmetric 18s

dobrichev wrote:
m_b_metcalf wrote:...This suggests that a proof is possible the the pattern always has at least one UA4 or one UA6.

There are 12 different two-row UA.
Four of them are UA18 and therefore are out of scope of this pattern, but I can't see any reason why any of the others UA of size 4, 6, 8 and 12 not to participate in the non-givens. In addition the non-givens from outside the 2-rows could result in larger UA.

You're right, of course.

Regards,

Mike

m_b_metcalf
2017 Supporter

Posts: 9395
Joined: 15 May 2006
Location: Berlin

### Re: Symmetric 18s

Hi, people!
coloin wrote:Ive just had a look at this pattern .....and it doesnt appear to have valid puzzles
Code: Select all
`+---+---+---+|xxx|xxx|xxx||...|.x.|...||...|.x.|...|+---+---+---+|xxx|.x.|xxx||xxx|.x.|xxx||xxx|.x.|xxx|+---+---+---+|xxx|.x.|xxx||xxx|.x.|xxx||xxx|.x.|xxx|+---+---+---+ `

I've fixed bugs in my code at last and done exhaustive search for this pattern. It turns out, this pattern has no valid puzzles (1 sec CPU time). The search was fast mainly because given pattern has high degree of symmetry. I counted (manually) 41472 automorphisms for it.

Is it possible to extend further this pattern by adding clues, preserving the property not having valid puzzles? (I.e. is this pattern maximal?) There are 2 e-d ways only for extending the pattern by 1 clue.
Code: Select all
`         A1                      A2+-----+-----+-----+     +-----+-----+-----+|. . x|. . .|. . .|     |. . x|. . .|. . .||. x x|. . .|. . .|     |. . x|. . .|. . .||x x x|x x x|x x x|     |x x x|x x x|x x x|+-----+-----+-----+     +-----+-----+-----+|. . x|x x x|x x x|     |. . x|x x x|x x x||. . x|x x x|x x x|     |. . x|x x x|x x x||. . x|x x x|x x x|     |. x x|x x x|x x x|+-----+-----+-----+     +-----+-----+-----+|. . x|x x x|x x x|     |. . x|x x x|x x x||. . x|x x x|x x x|     |. . x|x x x|x x x||. . x|x x x|x x x|     |. . x|x x x|x x x|+-----+-----+-----+     +-----+-----+-----+`
Patterns A1 and A2 contain as subsets the patterns which have definitely valid puzzles (see thread Investigation of one-crossing-free patterns), so they have valid puzzles too. Hence given pattern is maximal. Let me post it in 2 different views:
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 x|x x x|     |. . .|. x .|. . .|+-----+-----+-----+     +-----+-----+-----+|x . .|x x x|x x x|     |x x x|. x .|x x x||x . .|x x x|x x x|     |x x x|. x .|x x x||x . .|x x x|x x x|     |x x x|. x .|x x x|+-----+-----+-----+     +-----+-----+-----+`
This is "brother" pattern for Magic Pattern.

Serg

[Edited. I corrected a typo.]
Last edited by Serg on Fri Mar 08, 2013 7:01 am, edited 1 time in total.
Serg
2018 Supporter

Posts: 608
Joined: 01 June 2010
Location: Russia

### Re: Symmetric 18s

Serg wrote: .....I've fixed bugs in my code at last and done exhaustive search for this pattern. It turns out, this pattern has no valid puzzles (1 sec CPU time).

very impressive !
it would seem that no pattern gets past the unavoidable check then !

hopefully you will show us a mashive reduction in possible symmetric 18 patterns
and maybe the pattern will be of use in other searches

C
coloin

Posts: 1738
Joined: 05 May 2005

### Re: Symmetric 18s

Hi, coloin!
coloin wrote:very impressive !
it would seem that no pattern gets past the unavoidable check then !

hopefully you will show us a massive reduction in possible symmetric 18 patterns
and maybe the pattern will be of use in other searches

Thanks. This pattern definitely reduces search space for symmetric 18-clue patterns. I am planning to check it after investigation of crossings will be finished. (I hope we'll find additional useful patterns having no valid puzzles during that investigation.)

Serg
Serg
2018 Supporter

Posts: 608
Joined: 01 June 2010
Location: Russia

There might be a bug in the filtering process (see here).

This pattern has unique puzzles but is filtered out:
Code: Select all
`.............1......11.11.....1.1....1.....1..1.....1...1...1....1...1...1..1..1.`

Note that this pattern is in eleven's file.
Afmob

Posts: 130
Joined: 28 June 2011

### Re:

Hi, Afmob!
Afmob wrote:There might be a bug in the filtering process (see here).

This pattern has unique puzzles but is filtered out:
Code: Select all
`.............1......11.11.....1.1....1.....1..1.....1...1...1....1...1...1..1..1.`

Note that this pattern is in eleven's file.

You are right. This pattern must not be filtered out. I found a bug in my filtering program and fixed it. It turns out about 11000 patterns were filtered out wrongly. I'll edit my post you cited and upload new resulting file containing "rectified" patterns.

Serg
Serg
2018 Supporter

Posts: 608
Joined: 01 June 2010
Location: Russia

Thanks Serg! Now I've just got to find out which patterns I've missed so far.
Afmob

Posts: 130
Joined: 28 June 2011

### Re: Symmetric 18s

Hi, colleagues!
I've done additional filtering out patterns, not having valid puzzles, appling 40 maximal one-crossing-free patterns (see thread Investigation of one-crossing-free patterns) to the 199147-patterns list (file "sym18patterns_n-e_filtered4.zip"), based on original 294313-patterns eleven's list of possible 18-clue vertically symmetric patterns. I got 100728 patterns which potentially can have valid puzzles. Therefore, number of search space for 18-clue vertically symmetric patterns was reduced twice.
Code: Select all
`18-clue possible symmetric distributions (eleven's list + filtering)  N Distribution Patterns--------------------------  1  000022338      9  2  000022446     32  3  000033336     80  4  000111339      3  5  000111447     16  6  000111555     13  7  000112338      9  8  000112446     72  9  000112455     26 10  000113337     30 11  000113346     81 12  000113355     42 13  000113445     80 14  000114444     56 15  000122229      7 16  000122337    130 17  000122445    200 18  000133335    240 19  000222228     14 20  000222237     46 21  000222246     95 22  000222255     60 23  000222336    402 24  000222444    128 25  000223335    430 26  000223344    259 27  000233334    126 28  001111338      6 29  001111446     60 30  001111455     31 31  001112337     60 32  001112445    200 33  001113336    144 34  001113345    189 35  001113444    164 36  001122228     23 37  001122336    529 38  001122444    316 39  001123335    228 40  001123344    147 41  001133334    338 42  001222227    104 43  001222236    230 44  001222245    272 45  001222335    872 46  001223334    698 47  002222226    217 48  002222235    328 49  002222244    156 50  002222334    556 51  011111229      4 52  011111337     88 53  011111445     80 54  011112228     26 55  011112237     94 56  011112246    206 57  011112255    133 58  011112336    414 59  011112444    415 60  011113335    780 61  011113344    905 62  011122227    172 63  011122335   1218 64  011122344    505 65  011133333    703 66  011222226    672 67  011222235   1251 68  011222244   1093 69  011222334   3579   observed:  1 70  011223333   2604 71  012222225    443 72  012222333   1907 73  022222224   1168   observed:  2 74  022222233   1808   observed:  1 75  111111228     30 76  111111336    354 77  111111444    202 78  111112227    402 79  111112236   1032 80  111112245   1623 81  111112335   2316 82  111112344    911 83  111113334   4059 84  111122226   1844 85  111122235   3477 86  111122244   3105 87  111122334   8179   observed:  5 88  111123333   4194   observed:  1 89  111222225   4347 90  111222234   7458   observed:  4 91  111222333   7963   observed: 32 92  112222224   5872   observed:  4 93  112222233  10455   observed: 35 94  122222223   3145   observed: 24 95  222222222    938   observed: 12Total number of distributions    :     95Total number of patterns         : 100728Total number of observed patterns:    121Clues in pattern's central column0    31452   534524   410076    31248       0`

Zipped file can be loaded here.

It turns out, 18-clue vertically symmetric valid patterns containing 8 clues in the central column (c5) are impossible.

Serg

[Edited. I've added pattern #117 discovered by Afmob on the 6-th of August, 2013. Pattern has distribution 112222233.]
[Edited. I've added pattern #118 discovered by Afmob on the 3-rd of December, 2013. Pattern has distribution 112222224.]
[Edited. I've added pattern #119 discovered by Afmob on the 11-n of December, 2013. Pattern has distribution 111122334.]
[Edited. I've added pattern #120 discovered by Afmob on the 11-n of December, 2013. Pattern has distribution 111222234.]
[Edited. I've added pattern #121 discovered by Afmob on the 12 of December, 2013. Pattern has distribution 111222234.]
Last edited by Serg on Fri Dec 13, 2013 4:20 am, edited 4 times in total.
Serg
2018 Supporter

Posts: 608
Joined: 01 June 2010
Location: Russia

Thank you, Serg! This means that I "only" have to check about 66,000 patterns and then we know all symmetric 18 clue Sudokus having a unique solution. I think it's fair to estimate that the computation finishes this year.
Afmob

Posts: 130
Joined: 28 June 2011

PreviousNext