Symmetric 18s

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

Re: Symmetric 18s

Postby Serg » Sat Mar 02, 2013 5:31 pm

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

Re: Symmetric 18s

Postby coloin » Sat Mar 02, 2013 7:13 pm

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

Re: Symmetric 18s

Postby Serg » Sun Mar 03, 2013 5:32 am

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

Re: Symmetric 18s

Postby m_b_metcalf » Sun Mar 03, 2013 10:08 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8359
Joined: 15 May 2006
Location: Berlin

Re: Symmetric 18s

Postby coloin » Sun Mar 03, 2013 11:57 am

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

Re: Symmetric 18s

Postby dobrichev » Sun Mar 03, 2013 8:43 pm

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: 1316
Joined: 24 May 2010

Re: Symmetric 18s

Postby m_b_metcalf » Tue Mar 05, 2013 7:41 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8359
Joined: 15 May 2006
Location: Berlin

Re: Symmetric 18s

Postby Serg » Wed Mar 06, 2013 10:01 pm

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

Re: Symmetric 18s

Postby coloin » Thu Mar 07, 2013 10:50 pm

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

Re: Symmetric 18s

Postby Serg » Fri Mar 08, 2013 7:10 am

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

Postby Afmob » Wed Apr 10, 2013 7:04 am

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:

Postby Serg » Thu Apr 11, 2013 8:26 am

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

Postby Afmob » Thu Apr 11, 2013 10:55 am

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

Postby Serg » Sun Jun 09, 2013 8:43 pm

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

Total number of distributions    :     95
Total number of patterns         : 100728
Total number of observed patterns:    121


Clues in pattern's central column

0    3145
2   53452
4   41007
6    3124
8       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
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Postby Afmob » Mon Jun 10, 2013 8:15 am

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

Return to General