Symmetric 18s

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

Re: Symmetric 18s

Postby tarek » Fri Apr 11, 2014 8:28 pm

So the interest was in:

Any Symmetric 17
Orthogonally symmetric 18
Fully symmetric 20

3 things:

1. To check if anybody has checked the Fully symmetric 20s patterns that we have puzzles for then remove 2 clues for an orthogonal 18 & check that pattern for puzzles!!!!
2. Symmetrize the 49k+ 17s as much as possible to an orthogonally symmetric target. The puzzles which are off by 1 or 2 will be good candidates for a new orthogonally symmetric 18 search seeds.
3. Maybe we should move now to orthogonally symmetric 19s :D :D :D !!!
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Re: Symmetric 18s

Postby coloin » Mon Apr 21, 2014 3:16 pm

Well I think all the orthogonal symmetric 18s have been found.
There are too many orthogonal 19s to contemplate ......

And there appears to be an ever expanding spree of diagonally symmetric 18s ......

It would be nice to devise a way of classifying the patterns the way JPF did with the fully symmetric puzzles

The number of patterns isnt as many as serg outlined - as a diagonally smmetric 18 which has no clues on the diagonal symmetry line sometimes can be morphed into a puzzle with 2 or more clues on the diagonal. Some 2 clues will actually be 4.

Once i get fed up generating them i will scan for the apparently hardest.

This one - with 8 clues on the diagonal took a lot to find ... and there wont be many
Code: Select all
+---+---+---+
|1..|.2.|...|
|.2.|..4|.5.|
|..3|...|..6|
+---+---+---+
|...|5..|...|
|6..|...|7..|
|.8.|..3|...|
+---+---+---+
|...|.6.|1..|
|.4.|...|.2.|
|..5|...|..8|
+---+---+---+  rather perfect
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Symmetric 18s

Postby blue » Tue Apr 22, 2014 12:54 am

coloin wrote:The number of patterns isnt as many as serg outlined - as a diagonally smmetric 18 which has no clues on the diagonal symmetry line sometimes can be morphed into a puzzle with 2 or more clues on the diagonal. Some 2 clues will actually be 4.

Serg wrote:Crude estimate of lower bound can be obtained by dividing 2.4 x 10^9 by 6^4 - there should be not less than 2 x 10^6 18-clue essentially different diagonally symmetric patterns.

There are 2,085,966 of them.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Symmetric 18s

Postby Serg » Tue Apr 22, 2014 6:30 am

Hi, blue!
blue wrote:
Serg wrote:Crude estimate of lower bound can be obtained by dividing 2.4 x 10^9 by 6^4 - there should be not less than 2 x 10^6 18-clue essentially different diagonally symmetric patterns.

There are 2,085,966 of them.

Impressive result! How did you calculate those patterns?

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

Re: Symmetric 18s

Postby blue » Tue Apr 22, 2014 8:27 pm

Hi Serg,

Nothing fancy (unfortunately) ... just generation, canonicalization, and counting "first hits" on the canonicalized patterns.
I did something in the generation phase to reduce the 2.4e+9 inputs to 186e+6 -- requiring the clue positions on the main diagonal, to be "minlex", with an even clue count, before filling the remaining parts out to 18 clue positions total.

Best Regards,
Blue.

P.S.: These two patterns were counted as one, even though the transformation that connects them, isn't one of the (2*)6^4 that preserve diagonal symmetry.

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
blue
 
Posts: 573
Joined: 11 March 2013

Re: Symmetric 18s

Postby coloin » Tue Apr 22, 2014 9:27 pm

Very nice job - and looks like not many symmetrical morphs will have different clue counts on the diagonal. And as you say they are removed with canonicalizing the pattern.

The number [average 50 ? ] of different puzzles per pattern makes me wonder that not many of the patterns will have zero puzzles.
If half the patterns have puzzles - thats 50 million puzzles.
Which would make one in 30 puzzles diagonally symmetric [surely not !] I dont think are any lists of randomly generated 18s any where.

The puzzle with 8 clues on the diagonal may well be the only one - and only one other puzzle [non-sym] within {-2+2}.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Symmetric 18s

Postby Afmob » Wed Apr 23, 2014 7:08 am

How about counting all 18 clue patterns which are diagonally symmetric with regards to both diagonals like this pattern?
Code: Select all
. X . | . . . | . . .
X . . | . . . | . X .
. . X | X . X | . . .
------+-------+------
. . X | X . . | X . .
. . . | . . . | . . .
. . X | . . X | X . .
------+-------+------
. . . | X . X | X . .
. X . | . . . | . . X
. . . | . . . | . X .

If the number isn't too high it might be feasible to go through all patterns.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby Serg » Wed Apr 23, 2014 5:51 pm

Hi, all!
Here is calculation of the number of possible 18-clue patterns, having double diagonal symmetries (main diagonal and antidiagonal).
Code: Select all
Layout of sudoku puzzles, having double diagonal symmetries (main diagonal and antidiagonal symmetry axes).
Area "A" contains 1 cell.
Area "B" contains 8 cells.
Area "C" contains 16 cells.

B C C | C C C | C C B
. B C | C C C | C B .
. . B | C C C | B . .
------+-------+------
. . . | B C B | . . .
. . . | . A . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

Let a - number of clues in "A" area of solution grid (see the picture above), b - number of clues in "B" area, c - number of clues in "C" area. Then for each 18-clue pattern, having double diagonal symmetries, this equation is valid: a + 2b + 4c = 18.

You can see that a must be always zero to get even number on the left side of the equation. c can be 1, 2, 3, 4. Let's consider these all possible 4 cases. We should calculate number of patterns for all cases and then to sum that numbers to obtain total number of possible patterns. Number of possible patterns in the "C" area is described by formula n!/(k!*(n-k)!), where n = 16 - total number of cells in the "C" area, k - number of clues in the "C" area. This number must be multiplied by number of placing clues in the "B" area - m!/(p!*(m-p)!), where m = 8 - total number of cells in the "B" area, p - number of clues in the "B" area.

1. Area "C" contains 1 clue. k = 1, p = 7; number of patterns = 16 x 8 = 128.
2. Area "C" contains 2 clues. k = 2, p = 5; number of patterns = 120 x 56 = 6720.
3. Area "C" contains 3 clues. k = 3, p = 3; number of patterns = 560 x 56 = 31360.
4. Area "C" contains 4 clues. k = 4, p = 1; number of patterns = 1820 x 8 = 14560.

Total number of 18-clue double diagonal symmetric patterns: 52,768.

To calculate (approximately) number of essentially different 18-clue double diagonal symmetric patterns, I propose to count pattern-independent "true" automorhisms, i.e. automorphisms which are composed from pattern-independent ("true") basic VPTs such that each basic VPT
1. Belongs to common basic VPT family - bands/stacks permutations, permutations of rows (columns) in a band (stack), transposing.
2. Transform any double diagonal symmetric pattern to another double diagonal symmetric pattern, i.e. preserves double diagonal symmetry.
3. Is not trivial, i.e. doesn't coincide with transformation "Do nothing" for given class of patterns.

I see such pattern-independent "true" basic VPTs:
1. Mirroring around vertical symmetry axis (stacks B147/B369 and columns c1/c3, c4/c6 and c7/c9 swapping) (2 ways).
2. Rows permutations within the upper band and correlated rows permutations within the lower band, plus correlated column permutations within B147 and B369 stacks (6 ways).
3. Rows r4/r6 permutations within the middle band and correlated column c4/c6 permutations within B258 stack (2 ways).

So, alone pattern has at most 2 x 6 x 2 = 24 "true" automorphisms. (Hope I am not wrong.)

To get rough estimate of lower bound of essentially different 18-clue double diagonal symmetric patterns, one can divide total number of pattern by number of "true" automorphisms. Lower bound of e-d patterns: 52768/24 = 2200 (approx.)

I think real number of essentially different patterns is substaintially higher. (Numbers 52,768 and 24 are too low to get correct estimate.)

Serg
[Edited. I refined automorphisms description and correct VPT #1 definition.]
Last edited by Serg on Thu Apr 24, 2014 4:58 pm, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symmetric 18s

Postby blue » Wed Apr 23, 2014 7:41 pm

Those are the right numbers. I get 2580 patterns in the end.

Like before, there's some extra reduction due to patterns like these two, that are related by a transformation that doesn't normally preserve double diagonal symmetry.

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 . .
blue
 
Posts: 573
Joined: 11 March 2013

Re: Symmetric 18s

Postby Afmob » Thu Apr 24, 2014 3:53 pm

I can confirm the 2,580 ED patterns. Furthermore 232 patterns have at least two rows in a band without a clue, so they don't need to be checked. I think I will start analyzing the remaining patterns tomorrow.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Symmetric 18s

Postby Serg » Thu Apr 24, 2014 5:18 pm

Hi, blue!
blue wrote:Those are the right numbers. I get 2580 patterns in the end.

Glad to see correctness of my estimates. Could you post that 2580 patterns and 2 x 10^6 diagonally symmetric patterns?
blue wrote:Like before, there's some extra reduction due to patterns like these two, that are related by a transformation that doesn't normally preserve double diagonal symmetry.

This is the main obstacle in accurate calculation of symmetric e-d patterns. VPTs being applied to double diagonal symmetry patterns don't form a "group acting on a set", if we assume set of patterns having double diagonal symmetry. Some VPTs preserves this symmetry constraint, but others - don't preserves symmetry for some patterns and preserves symmetry for other patterns. For this reason classic combinatorial techniques such as Burnside's Lemma, PET are not applicable to calculation of symmetric e-d patterns.

Maybe sometime someone will invent algorithm to do such calculations.

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

Re: Symmetric 18s

Postby coloin » Thu Apr 24, 2014 7:04 pm

I have now over 500 patterns which have symmetric puzzles. The average number of puzzles per pattern is 70.

There maybe more diagonally symmetric puzzles than previously realized - { what is the % ? ]
There maybe many patterns excluded by serg's rules - or a previously undiscovered maximal impossible pattern is causing it.
Maybe a neighbourhood vicinity search preferentially finds those patterns with more puzzles.... likely

Except there is a big difference between 0 puzzles and 70 puzzles in any one "similarish" pattern.

Hopefully we will find out.

I will check how many of the patterns i have exhibit double diagonal symmetry.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: Symmetric 18s

Postby blue » Fri Apr 25, 2014 4:26 am

Serg wrote:Could you post that 2580 patterns and 2 x 10^6 diagonally symmetric patterns?


The double diagonal puzzles are attached.
I don't have any way to share the other file (It's 17M zipped).

For Afmob, the double double diagonal puzzles have a + or - at the end of the line.
The ones with a '-' won't have puzzles. They can be mapped to subpatterns of one of the "magic patterns" in this post

This is the correct file. Sorry for the confusion.
There are (still) 1696 shapes that are marked as "viable".

dd-18.zip
(20.66 KiB) Downloaded 110 times
blue
 
Posts: 573
Joined: 11 March 2013

Re: Symmetric 18s

Postby Serg » Fri Apr 25, 2014 7:06 pm

Hi, blue!
blue wrote:The double diagonal puzzles are attached.

Thanks!
blue wrote:I don't have any way to share the other file (It's 17M zipped).

See thread How to attach large file to the post.

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

Re: Symmetric 18s

Postby Serg » Fri Apr 25, 2014 10:43 pm

Hi, blue!
blue wrote:There are (still) 1696 shapes that are marked as "viable".

I cross-checked your filtering results and now confirm their correctness. 884 patterns only can be filtered out by applying "40 maximal patterns list". So, 1696 patterns (namely marked by "+") can potentially have valid patterns.

Here is filtering patterns champion.
Code: Select all
. . . . . x . x x     Filtering pattern is applicable 523 times
. . . . . x . x x
. . . . . x . x x
. . . x x x x x x
. . . x x x x x x
x x x x x x x x x
. . . x x x x x x
x x x x x x x x x
x x x x x x x x x

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

PreviousNext

Return to General