Enumeration of symmetrical patterns

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

Enumeration of symmetrical patterns

Postby Serg » Sun Jan 21, 2018 11:45 pm

Hi, people!
I propose to discuss symmetrical patterns enumeration problem.

The first time I encountered this problem in the thread Symmetric 18s. In this thread 18-clue sudoku puzzles, having vertical symmetry, were discussed, and essentially different clues configurations (i.e. patterns) were collected. I tried to calculate mathematically number of essentially different 18-clue symmetrical patterns, but couldn't do it. The problem was decided by "brute force" method, by generation of all possible 18-clue symmetrical patterns and filtered out isomorphs.

Further in the cited thread 18-clue double diagonal symmetrical patterns were investigated (see Afmob's post in the thread Symmetric 18s). Again, there were no methods to compute exact number of such patterns. The problem was solved by generation of all possible patterns.

The next case - enumeration of fully symmetrical patterns - the thread "Fully symmetrical puzzles" (see, for example, gfroyle's post here and JPF's post here). The problem was solved by generation of all possible patterns (number of such patterns is 2^15 only) and applying all possible isomorphic transformations.

My goal is to find mathematical method of symmetrical patterns enumeration, to find mathematical base (like conjugacy classes technique, Burnside's Lemma, etc.), substantially reducing complexity of original problem. Such a method would make it possible to obtain exact number very fast for the cases cited above and even enumerate patterns/grids in more complicated cases, such as enumeration of essentially different P-Sudoku (aka "Sudoku DG") solution grids, etc.

Let's consider a problem of enumerating fully symmetrical patterns, as an example.

Definition
Pattern is 9x9 binary matrix (i.e. containing "0" or "1" in each cell). Cell containg "1" means that sudoku puzzle, constructed on the base of this pattern must have clue in this cell. Cell containg "0" means that sudoku puzzle, constructed on the base of this pattern must not have clue in this cell. So, pattern defines a family of sudoku puzzles. These puzzles may have equal or different digits in the same cells, but all these puzzles have the same structure (the same pattern of clues). Here is an example of (fully symmetrical) pattern.
Code: Select all
1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 1

Very often cells containing clues are marked by "x", cells not containing clues are marked by ".".

Total number of "all different" fully symmetrical patterns (i.e. patterns having vertical, horizontal, diagonal and antidiagonal symmetries simultaneously) is 2^15 or 32768. But how many are there essentially different patterns?

It is rather evident, that there are 6 "universal" isomorphic transformations, which transform any fully symmetrical pattern to another fully symmetrical pattern, all transformation having similar type: permutation of rows in B123 band AND the same permutation of columns in B147 stack AND "mirrored" permutation of rows in B789 band AND the same "mirrored" permutation of columns in B369 stack. "Mirrored" permutation means that r1/r2 permutation must be supplemented by r8/r9 permutation, left cyclical shift of columns c1-c3 must be supplemented by right cyclical shift of columns c7-c9, etc.

Besides those "universal" isomorphic transformations, there are "non-universal" transformations, which transform some fully symmetrical patterns to other fully symmetrical patterns, but drop fully symmetry for certain fully symmetrical patterns.

It looks like JPF was the first, who counted essentially different fully symmetrical patterns. It turns out, there are 6016 such patterns. Later this number was confirmed and there is no doubt that this is true.

So, I invite everyone to develop mathematical approach for enumeration of essentially different fully symmetrical patterns.

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Mon Jan 22, 2018 1:36 am

Count me in! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Mon Jan 22, 2018 2:48 am

Hi Serg!

I thought I would start with an attempt to define the Symmetric Pattern "universal transformations" in GAP, and to my amazement it appears to have worked first time! :?

I defined SymP group with just two generator elements, one for the "swap r1, r2" transformation and one for the "swap r2, r3", since I guessed that these would suffice to define the group, and sure enough I get 6 elements, 3 conjugacy classes which have 1 (identity), 3, and 2 members respectively.

So I can plug these classes back into my test rig and see if they work, eg getting the correct number of 6528 different patterns under these universal transformations.

You probably never really noticed, being a Sudoku buff, but I spent much of my early time on this forum building and discussing a Kakuro puzzle generation system.

One aspect of that was grid template generation, which is very much like the Symmetric Patterns problem for Sudoku, albeit with arbitrary grid sizes (NR x NC). And they had either half (diagonal reflection) or full symmetry (most Kakuro grids are half-symmetric). But the principles are essentially the same, binary matrix patterns.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Mon Jan 22, 2018 3:50 pm

Serg wrote:Total number of "all different" fully symmetrical patterns (i.e. patterns having vertical, horizontal, diagonal and antidiagonal symmetries simultaneously) is 2^15 or 32768. But how many are there essentially different patterns?


We can make a different pattern for every setting of the 4x4 box in the top left corner, right? So that's 2^16. Then (and this only applies because 9 is odd) we can set 4 cells of r5/c5 in 2^4 ways, times 2 for center square, that's 2^21, isn't it?

[EDIT] Oops! The 4x4 box with the "seed" pattern has to have diagonal symmetry, so that's 2^4 x 2^6 = 2^10 for the 4x4 box, so 2^10 x 2^4 x 2 is 2^15. All good!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Serg » Mon Jan 22, 2018 10:58 pm

Hi, Mathimagics!
Serg wrote:Total number of "all different" fully symmetrical patterns (i.e. patterns having vertical, horizontal, diagonal and antidiagonal symmetries simultaneously) is 2^15 or 32768. But how many are there essentially different patterns?

Code: Select all
 A A A A A . . . .
 . A A A A . . . .
 . . A A A . . . .
 . . . A A . . . .
 . . . . A . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .
 . . . . . . . . .

I mean, that cells marked by "A" may contain "0" or "1" (totally 15 cells), but the rest cells must have values defined by vertical, horizontal, diagonal and antidiagonal symmetries.

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Enumeration of symmetrical patterns

Postby Serg » Mon Jan 22, 2018 11:32 pm

Hi, Mathimagics!
Mathimagics wrote:I thought I would start with an attempt to define the Symmetric Pattern "universal transformations" in GAP, and to my amazement it appears to have worked first time! :?

It's quite possible that you are the first doing that. I counted 6528 different patterns by "brute force" method, without equivalence classes.
Mathimagics wrote:I defined SymP group with just two generator elements, one for the "swap r1, r2" transformation and one for the "swap r2, r3", since I guessed that these would suffice to define the group, and sure enough I get 6 elements, 3 conjugacy classes which have 1 (identity), 3, and 2 members respectively.

Yes, 2 transformations generate necessary group, but "swap r1, r2" must be completed by "swap r8, r9", "swap c1, c2" and "swap c8, c9" fo present true first isometric transformation.
Mathimagics wrote:So I can plug these classes back into my test rig and see if they work, eg getting the correct number of 6528 different patterns under these universal transformations.

Yes. You should know important trick unique to patterns - pattern is fixed by a transformation iff cells of every permutation cycle of this transformation
all have "0" or all have "1".
Mathimagics wrote:You probably never really noticed, being a Sudoku buff, but I spent much of my early time on this forum building and discussing a Kakuro puzzle generation system.

I noticed your work, but I have a little interest in kakuro area. I think sudoku has higher mathematical potential because it is more regular. But similar kakuro problems, as to me, are more different. For example, as far as I know, it is not defined yet - what kakuro puzzles are isomorphic, equivalent, etc.

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Tue Jan 23, 2018 3:29 am

Ok, I can confirm that my Burnside's Lemma calculation for the group shows 6528 essentially different patterns. We know this is actually too many, but it's a good start.

And! I think I have cracked the code, so to speak. I believe that I can tell you the correct value for the number of essentially different fully symmetric patterns for any matrix size N. No computer required.

I'm just tidying up my notes and will describe this result soon.

Serg wrote:For example, as far as I know, it is not defined yet - what kakuro puzzles are isomorphic, equivalent, etc.

There is only one obvious form of isomorphism that we can describe just now, that which replaces each digit D in the solution with 10 - D.

serg wrote:I think sudoku has higher mathematical potential because it is more regular.

But did you know that, in terms of the range of solving difficulty, Sudoku is very limited. But a Kakuro puzzle on the same grid pattern can be constructed with effectively an arbitrary level of difficulty.

They can be easy, or extremely difficult, effectively impossible to solve by hand, even on quite small grid sizes (eg 7x7).

And that is what fascinates me ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Tue Jan 23, 2018 12:38 pm

[EDIT] Apologies, everybody. This post was rubbish!
Last edited by Mathimagics on Thu Jan 25, 2018 8:50 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Tue Jan 23, 2018 1:34 pm

[EDIT] Apologies, everybody. This too was rubbish!
Last edited by Mathimagics on Thu Jan 25, 2018 8:51 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Serg » Wed Jan 24, 2018 11:22 pm

Hi, Mathimagics!
Mathimagics wrote:The source of the "intersecting orbits" of our Symmetric Pattern symmetry group is simply those corner patterns which are themselves fully symmetric.

What do you mean?

Here are some definitions to simplify our discussions.

Definition 1
VPT Group, Validity Preserving Transformations Group is group of transformations preserving validity of any valid sudoku puzzle or solution grid. This group contains 3359232 transformations and is generated by following set of transformations.
1. Transposing.
2. Permutations of bands.
3. Permutations of stacks.
4. Permutations of rows within band B123.
5. Permutations of rows within band B456.
6. Permutations of rows within band B789.
7. Permutations of columns within stack B147.
8. Permutations of columns within stack B258.
9. Permutations of columns within stack B369.

Definition 2
Two sudoku puzzles/grids/patterns are essentially the same or equivalent if there is VPT transforming one puzzle/grid/pattern to another. Otherwise these puzzles/grids/patterns are essentially different or non-equivalent.

Definition 3
FSPT Group, Full Symmetry Preserving Transformations Group is group of transformations preserving full symmetry of any fully symmetric pattern. This group contains 6 following transformations.
1. "Do nothing".
2. Swap of rows r1/r2 AND swap of rows r8/r9 AND swap of columns c1/c2 AND swap of columns c8/c9.
3. Swap of rows r1/r3 AND swap of rows r7/r9 AND swap of columns c1/c3 AND swap of columns c7/c9.
4. Swap of rows r2/r3 AND swap of rows r7/r8 AND swap of columns c2/c3 AND swap of columns c7/c8.
5. Up cyclic shift of rows r1-r3 AND down cyclic shift of rows r7-r9 AND left cyclic shift of columns c1-c3 AND right cyclic shift of columns c7-c9.
6. Down cyclic shift of rows r1-r3 AND up cyclic shift of rows r7-r9 AND right cyclic shift of columns c1-c3 AND left cyclic shift of columns c7-c9.

Definition 4
Two fully symmetrical sudoku patterns are fully symmetrically equivalent or fs-equivalent if there is FSPT transforming one pattern to another. Otherwise these patterns are fully symmetrically different or fs-different.

Definition 5
Image of sudoku puzzle/grid/pattern is result of applying a transformation to sudoku puzzle/grid/pattern.

Definition 6
Orbit of sudoku puzzle/grid/pattern is set of this puzzle/grid/pattern's images after applying to it given transformations group. (One can say: "Orbit of a puzzle/grid/pattern under given transformations group".) All puzzles/grids/patterns within the same orbit are equivalent in some sense. When we count non-equivalent in some sense or different in some sense puzzles/grids/patterns for given transformations group, we are counting orbits.

Here is an example of connected orbits (this is Gordon Royle's example).
Code: Select all
     Orbit 1
        #1
x . . . . . . . x
. x . . . . . x .
. . x . . . x . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . x . . . x . .
. x . . . . . x .
x . . . . . . . x


     Orbit 2
        #2                    #3                    #4
. x . . . . . x .     . . x . . . x . .     x . . . . . . . x
x . . . . . . . x     . x . . . . . x .     . . x . . . x . .
. . x . . . x . .     x . . . . . . . x     . x . . . . . x .
. . . . . . . . .     . . . . . . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .     . . . . . . . . .
. . x . . . x . .     x . . . . . . . x     . x . . . . . x .
x . . . . . . . x     . x . . . . . x .     . . x . . . x . .
. x . . . . . x .     . . x . . . x . .     x . . . . . . . x

Orbit 1 - orbit of the pattern #1 under FSPT group. You can see that the orbit consists from 1 pattern. So, this pattern remains unchanged after applying any of FSPT. Therefore, this pattern has 6 fs-automorphisms.

Orbit 2 - orbit of the pattern #2 under FSPT group. You can see that the orbit consists from 3 patterns. So, this pattern has 2 fs-automorphisms (2 = 6/3).

If we consider FSPT group for fully symmetrical patterns, we must treat pattern #1 and pattern #2 (#3, #4) as fs-different. But if we consider VPT group, patterns #1, #2, #3 and #4 are equivalent, because we can transform pattern #1 to pattern #2 by transformation "swap of columns c1/c2 AND swap of columns c8/c9". All these 4 patterns form now the same orbit under VPT group. This is why I say "orbit connection", but not "orbit intersection"! One can say too "orbit union", but not "orbit intersection".

What do you mean saying
Mathimagics wrote:The source of the "intersecting orbits" of our Symmetric Pattern symmetry group is simply those corner patterns which are themselves fully symmetric.


Mathimagics wrote:Then NEDP (number of essentially different patterns) is the value returned by the group's Burnside calculation, call this NEDPB, minus the NDDP count (number of double-diagonal symmetric patterns).

Why we should subtract number of double-diagonal symmetric patterns?

Serg

[Edited. I refined some definitions and corrected a typo.]
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Fri Jan 26, 2018 12:29 am

Hi Serg,

Apologies for the confusion caused by my previous posts, which I have now removed! I wandered off the reservation there ... :?

And thanks for the clarity of your definitions ... well worth it and much appreciated.

Why should we subtract DD patterns? Because I still think that they do account for the difference between the 6528 count returned by the Burnside Lemma calculation on the FSPT group (ie the # of fs-different patterns), and the 6016 count that we have for the # of essentially different patterns.

I'm looking into this further.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Sat Jan 27, 2018 1:59 am

Ok, let's consider DD3 patterns. These are patterns with double-diagonal symmetry in the 3x3 corners.

It seems that only these cases give rise to the orbit connection problem. Now look at this result of the Burnside Lemma process expanded to process each FSPT transformation individually:

Code: Select all
  --------------------------------
  CC        NINV    DD3?  N      Y     
  --------------------------------
  C[2,1]    2048       1536    512
  C[2,2]    2048       1536    512   
  C[2,3]    2048          0   2048

  C[3,1]     128          0    128
  C[3,2]     128          0    128
  --------------------------------
  NEDP      6528     NEDP*    6016
  --------------------------------


NINV is # of invariant patterns for each transformation.

DD3? indicates how many of these invariant patterns have DD3 property.

NEDP (# of FS-different grids) is (32768 + 3 x 2048 + 2 x 128) / 6 = 6528.

Interestingly, ALL invariants for 3 of the 5 transformations have DD3 property, but for the first two transformations only one in 4 have DD3 property.

And if we redo the NEDP calculation counting ONLY the DD3 invariants we get the desired result NEDP* (# of essentially different patterns) as (32768 + (2048 + 2 x 512) + 2 x 128) / 6 = 6016.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Enumeration of symmetrical patterns

Postby Serg » Sat Jan 27, 2018 8:07 pm

Hi, Mathimagics!
Interesting, but I have too many questions ...
Mathimagics wrote:Ok, let's consider DD3 patterns. These are patterns with double-diagonal symmetry in the 3x3 corners.

Do you mean following 16 possible patterns in B1,B3,B7,B9 boxes?
Code: Select all
  P1      P2      P3      P4      P5      P6      P7      P8      P9     P10     P11     P12     P13     P14     P15     P16

. . .   . . .   x . .   . . x   x . .   . . x   x . x   . x .   x . x   . x .   x x .   . x x   x x .   . x x   x x x   x x x
. . .   . x .   . . .   . . .   . x .   . x .   . . .   x . x   . x .   x x x   x . x   x . x   x x x   x x x   x . x   x x x
. . .   . . .   . . x   x . .   . . x   x . .   x . x   . x .   x . x   . x .   . x x   x x .   . x x   x x .   x x x   x x x

Mathimagics wrote:It seems that only these cases give rise to the orbit connection problem.

Why?
Mathimagics wrote:Now look at this result of the Burnside Lemma process expanded to process each FSPT transformation individually:

Do you mean, that no conjugacy classes are used, but fixed patterns are calculated for each FSPT?
Mathimagics wrote:
Code: Select all
  --------------------------------
  CC        NINV    DD3?  N      Y     
  --------------------------------
  C[2,1]    2048       1536    512
  C[2,2]    2048       1536    512   
  C[2,3]    2048          0   2048

  C[3,1]     128          0    128
  C[3,2]     128          0    128
  --------------------------------
  NEDP      6528     NEDP*    6016
  --------------------------------

What values are in "CC" column?

Serg
Serg
2018 Supporter
 
Posts: 858
Joined: 01 June 2010
Location: Russia

Re: Enumeration of symmetrical patterns

Postby eleven » Sat Jan 27, 2018 11:02 pm

These patterns are Sudoku equivalent (swap r13), but not symmetry equivalent:

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 .
eleven
 
Posts: 3081
Joined: 10 February 2008

Re: Enumeration of symmetrical patterns

Postby Mathimagics » Sat Jan 27, 2018 11:32 pm

Hi Serg

  • Yes, there are just those 16 patterns for fully symmetric 3x3 (DD3).

  • The table shows individual automorphism (invariant) counts for each of the 5 FSPT transformations (identity transformation is omitted) rather than Burnside method of just one transformation from each conjugacy class. "CC" labels each transformation by conjugacy class. I have listed the FSPT transformations by conjugacy class membership below.

This should answer 2 of your questions. The third question was "why should only DD3 patterns provide orbit connections?". I admit that this is only conjecture, but one that is apparently supported by the evidence. The number 512 just keeps popping up:

  • 512 = 6528 (NEDP under FSPT) - 6016 (NEDP under VPT)
  • 512 = number of automorphisms for DD3 patterns under FSPT transformations [2,1] and [2,2]
  • 512 = number of fully-symmetric 9x9 patterns.

FSPT group by conjugacy class [CC#, #]:
Hidden Text: Show
Code: Select all
[1,1] ()
[2,1] (2,3)(7,8)(10,19)(11,21)(12,20)(13,22)(14,23)(15,24)(16,26)(17,25)(18,27)(29,30)(34,35)(38,39)(43,44)(47,48)(52,53)(55,64)(56,66)(57,65)(58,67)(59,68)(60,69)(61,71)(62,70)(63,72)(74,75)(79,80)
[2,2] (1,11)(2,10)(3,12)(4,13)(5,14)(6,15)(7,16)(8,18)(9,17)(19,20)(26,27)(28,29)(35,36)(37,38)(44,45)(46,47)(53,54)(55,56)(62,63)(64,74)(65,73)(66,75)(67,76)(68,77)(69,78)(70,79)(71,81)(72,80)
[2,3] (1,21)(2,20)(3,19)(4,22)(5,23)(6,24)(7,27)(8,26)(9,25)(10,12)(16,18)(28,30)(34,36)(37,39)(43,45)(46,48)(52,54)(55,75)(56,74)(57,73)(58,76)(59,77)(60,78)(61,81)(62,80)(63,79)(64,66)(70,72)
[3,1] (1,11,21)(2,12,19)(3,10,20)(4,13,22)(5,14,23)(6,15,24)(7,18,26)(8,16,27)(9,17,25)(28,29,30)(34,36,35)(37,38,39)(43,45,44)(46,47,48)(52,54,53)(55,74,66)(56,75,64)(57,73,65)(58,76,67)(59,77,68)(60,78,69)(61,81,71)(62,79,72)(63,80,70)
[3,2] (1,21,11)(2,19,12)(3,20,10)(4,22,13)(5,23,14)(6,24,15)(7,26,18)(8,27,16)(9,25,17)(28,30,29)(34,35,36)(37,39,38)(43,44,45)(46,48,47)(52,53,54)(55,66,74)(56,64,75)(57,65,73)(58,67,76)(59,68,77)(60,69,78)(61,71,81)(62,72,79)(63,70,80)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Next

Return to General