Symmetric 18s

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

Re: Symmetric 18s

Postby Serg » Mon Apr 16, 2012 9:57 pm

Hi, colleagues!
I found an arithmetic error in my calculations (manual calculations are error-prone). eleven, you are right - total numbers of 18-clue symmetric patterns is still 2,402,330,656.

About filtering out patterns not complying to composition rules. I have proper C code, but embedded in another program. I'll try to code autonomous utility (reading eleven's file) ASAP.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby ronk » Mon Apr 16, 2012 10:52 pm

eleven wrote:With 2 automorphisms each puzzle has 3 equivalents with the same pattern.

Understanding automorphism eluded me for a long time, so I could still be wrong, but ... shouldn't that be "1 equivalent?"
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Symmetric 18s

Postby coloin » Tue Apr 17, 2012 12:06 am

I think its achieved by swapping c46 = 2
swapping stacks 1 and 3 and swapping c123 and c789 = 2

so at least 4 equivalents for each pattern
C
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: Symmetric 18s

Postby ronk » Tue Apr 17, 2012 1:20 am

coloin wrote:I think its achieved by swapping c46 = 2
swapping stacks 1 and 3 and swapping c123 and c789 = 2

so at least 4 equivalents for each pattern

OK, I should have been thinking about vertical symmetry, then automorphisms >= 4, not 2.

[edit: add the following]

here gsf wrote:my solver has code to canonicalize fish exemplars
a fallout of that process is the number of automorphisms

Use gsf's program on a file containing all known symmetric 18s to verify automorphisms >= 4.
Last edited by ronk on Tue Apr 17, 2012 5:13 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Afmob » Tue Apr 17, 2012 6:06 am

I currently have analyzed about 3000 patterns and I can confirm that the first 2147 patterns have no uniquely solvable 18 clue Sudoku.

eleven, I look into your question.

Edit: This one has the most essentially different puzzles of all patterns with a total of 4,693,836,890 essentially different puzzles and 4 automorphisms.
Code: Select all
....X......X...X...X.....X....X.X.....X...X..X.......X...XXX....X.....X.X.......X


It should take about a day to solve all those puzzles. An honourable mention goes to
Code: Select all
....X......X...X....X...X.....X.X....X.....X..X.....X....XXX...X.......XX.......X

with 1,146,653,411 essentially different puzzles and 32 automorphisms.
Afmob
 
Posts: 130
Joined: 28 June 2011

Postby Pat » Tue Apr 17, 2012 11:59 am

ronk wrote:
coloin wrote:
eleven wrote:With 2 automorphisms,
each puzzle has 3 equivalents with the same pattern

  • swapping c46
  • swapping stacks 1 and 3 and swapping c123 and c789
so at least 4 equivalents

OK, I should have been thinking about vertical symmetry, then automorphisms >= 4, not 2.

eleven + coloin are right

at least 2 automorphisms
    ==> each puzzle is part of a class of at least 4 automorphs
      i.e. has at least 3 automorphs
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Re:

Postby eleven » Tue Apr 17, 2012 5:30 pm

Afmob wrote:This one has the most essentially different puzzles of all patterns with a total of 4,693,836,890 essentially different puzzles and 4 automorphisms.
Code: Select all
....X......X...X...X.....X....X.X.....X...X..X.......X...XXX....X.....X.X.......X


It should take about a day to solve all those puzzles. An honourable mention goes to
Code: Select all
....X......X...X....X...X.....X.X....X.....X..X.....X....XXX...X.......XX.......X

with 1,146,653,411 essentially different puzzles and 32 automorphisms.

Thanks Afmob,
the first pattern is not very encouraging for this project. To solve all puzzles would probably take me 1 1/2 days on my PC on a single core.

I came across this one with 48 automorphs (dont know yet, if this is the maximum in the list).
Code: Select all
.............1.......1.1.....1...1....1...1....1...1....11111...1.....1.1.......1
eleven
 
Posts: 1559
Joined: 10 February 2008

Re: Symmetric 18s

Postby Afmob » Tue Apr 17, 2012 8:51 pm

Do you mean maximum number of automorphisms? While searching for the one with the most essentially different puzzles I found one with 576 automorphisms if I remember correctly but there might be patterns in your file with more automorphisms.

By the way, I mentioned the other pattern with 32 automorphisms because if you disregard the automorphisms it would have the highest number of puzzles (over 32 billion).
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby Serg » Tue Apr 17, 2012 9:38 pm

Hi, colleagues!
I filtered eleven's list of patterns by applying composition rules. Here is my program report.
Code: Select all
Composition rules filter (8 rules), version 1.0

Total number of processed patterns: 294742

Filtering statistics

Empty rows (columns): filtered out      0 patterns
Composition rule 1:   filtered out  22670 patterns
Composition rule 2:   filtered out  40853 patterns
Composition rule 3:   filtered out    379 patterns
Composition rule 4:   filtered out      0 patterns
Composition rule 5:   filtered out      0 patterns
Composition rule 6:   filtered out    420 patterns
Composition rule 7:   filtered out      0 patterns
Composition rule 8:   filtered out   5567 patterns

Totally filtered out patterns:  69889
               Valid patterns: 224853

Total program execution time: 6 seconds

Number of "rectified" patterns - 224853. So, eleven was right when he predicted not less than 200000 patterns after filtering out invalid patterns. I hoped for the better ... :( . On the other hand we can imagine that we have already done exhaustive search for 70000 patterns. Not so bad :) .

Zipped file with filtered patterns has size almost 1 MB. You know this forum limits alone attached file size to 256 Kb. So, I had to split entire file onto 4 parts - the first part is attached to this post, other 3 parts are attached to my 3 next (dummy) posts.

Sorry for spoiling this thread.

Serg
Attachments
sym18pat_filtered.zip
(147.98 KiB) Downloaded 108 times
Last edited by Serg on Tue Apr 17, 2012 9:47 pm, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby Serg » Tue Apr 17, 2012 9:44 pm

Part 2 of 4
You must rename this file after downloading to "sym18pat_filtered.z01" and move to the directory, containing 1st part of archive.
Attachments
sym18pat_filtered_z01.zip
(250 KiB) Downloaded 107 times
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby Serg » Tue Apr 17, 2012 9:44 pm

Part 3 of 4
You must rename this file after downloading to "sym18pat_filtered.z02" and move to the directory, containing 1st part of archive.
Attachments
sym18pat_filtered_z02.zip
(250 KiB) Downloaded 99 times
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby Serg » Tue Apr 17, 2012 9:46 pm

Part 4 of 4
You must rename this file after downloading to "sym18pat_filtered.z03" and move to the directory, containing 1st part of archive.
Now you can unzip entire archive.

Serg
Attachments
sym18pat_filtered_z03.zip
(250 KiB) Downloaded 100 times
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby eleven » Thu Apr 19, 2012 7:24 am

Fine, Serg,

I removed the remaining 304 equivalents and uploaded the file there.
eleven
 
Posts: 1559
Joined: 10 February 2008

Re: Symmetric 18s

Postby Serg » Fri Apr 20, 2012 4:23 am

Hi, eleven!
I loaded your file (without isomorphic duplicates). I have some ideas concerning additional filtering out patterns (but I don't expect significant search space reduction). I need several days to implement these ideas.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Postby Afmob » Fri Apr 20, 2012 6:47 am

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

PreviousNext

Return to General