Fully symmetrical invalid patterns

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

Re: Fully symmetrical invalid patterns

Postby Serg » Tue Mar 28, 2017 9:24 pm

Hi, blue!
blue wrote:To avoid (possible) confusion in the future, it might be good to explain things in a little more depth.

I am ready to discuss this project in details (if there will be someone's interest).
blue wrote:Explain how these two (valid) puzzles, fit into your outline ...

Code: Select all
4 7 . | . . . | . 5 3
2 . 5 | . . . | 8 . 7
. 3 . | . . . | . 6 .
------+-------+------
. . . | 5 7 2 | . . .
. . . | 4 . 3 | . . .
. . . | 1 8 9 | . . .
------+-------+------
. 8 . | . . . | . 7 .
3 . 2 | . . . | 9 . 8
1 6 . | . . . | . 3 4

Your second example (cited above) is more complicated than the first one. But it is superset of F77 pattern. Swap columns c4/c5 of your example to detect that resulting pattern is superset of F77.

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

Re: Fully symmetrical invalid patterns

Postby Afmob » Wed Mar 29, 2017 10:15 am

blue, your ED count for F11 with filtering is correct. It seems that I missed some a priori invalid puzzles in my first implementation. Nevertheless, the result of the first computation still holds since it didn't miss any (possible) valid puzzle.

The last days I tried getting the number of ED valid puzzles of F78, which has 25 clues and 512 automorphisms, to see if it is feasible to get the valid puzzle count for all valid patterns with at least 24 clues. For this I changed my implementation to use multiple CPU cores for one pattern instead of giving each available core one pattern only. The computation took about 2 days with 3 CPU cores with some breaks in between. Therefore I don't have the exact number of ED puzzles I had to check but (using an estimate) it should be at least 4.72e10 puzzles.

Here are all ED valid puzzles of F78:
Code: Select all
12.....6736.....48..7...5.....1.2.......3.......4.5.....3...2..21.....7594.....16
12.....6736.....58..7...4.....1.2.......3.......4.5.....3...1..21.....7495.....26
12.....6736.....84..7...5.....1.2.......3.......4.5.....3...2..21.....7594.....16
12.....6736.....85..7...4.....1.2.......3.......4.5.....3...1..21.....7495.....26
12.....4867.....29..3...6.....1.2.......3.......4.5.....8...4..29.....8535.....97
12.....4867.....92..3...6.....1.2.......3.......4.5.....8...4..25.....8939.....57
12.....6967.....25..8...1.....1.2.......3.......4.5.....4...2..25.....1678.....34

As you can see, we have a very small number of valid puzzles but a huge number of puzzles to be checked. So I think that with the current method, it is not feasible get the count for the other minimal valid patterns.

Edit: Corrected typo. Thanks Serg!
Last edited by Afmob on Thu Mar 30, 2017 4:36 am, edited 1 time in total.
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: Fully symmetrical invalid patterns

Postby Serg » Wed Mar 29, 2017 9:59 pm

Hi, Afmob!
Afmob wrote:Here are all ED valid puzzles of F78:
Code: Select all
12.....6736.....48..7...5.....1.2.......3.......4.5.....3...2..21.....7594.....16
12.....6736.....58..7...4.....1.2.......3.......4.5.....3...1..21.....7495.....26
12.....6736.....84..7...5.....1.2.......3.......4.5.....3...2..21.....7594.....16
12.....6736.....85..7...4.....1.2.......3.......4.5.....3...1..21.....7495.....26
12.....4867.....29..3...6.....1.2.......3.......4.5.....8...4..29.....8535.....97
12.....4867.....92..3...6.....1.2.......3.......4.5.....8...4..25.....8939.....57
12.....6967.....25..8...1.....1.2.......3.......4.5.....4...2..25.....1678.....34
F78 pattern aka "Fractal Pattern" has its own history, published in the thread Valid puzzles for Fractal Pattern.
Code: Select all
Pattern F78           Fractal Pattern

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

I use Fractal Pattern for exhaustive search programs "calibration" since 2011. Unfortunately, "Essential form" for fully symmetrical patterns doesn't preserve Fractal Pattern shape, so one can hardly recognize it.

Serg
Last edited by Serg on Fri Mar 31, 2017 7:58 am, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby JPF » Thu Mar 30, 2017 9:05 pm

Hi Serg,
Serg wrote:So, I can state that every fully symmetric pattern is "subset" or "superset".

I checked and I can confirm your results:
Every fully symmetric pattern is a subset of the 25 "invalid" patterns* or a superset of one of the 49 "valid" patterns.

Well done! A clever way to structure the set of 6016 ed-fully symmetric patterns.
* assuming your list of 25 invalids is correct.

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Fully symmetrical invalid patterns

Postby Serg » Fri Mar 31, 2017 8:07 am

Hi, JPF!
JPF wrote:I checked and I can confirm your results:
Every fully symmetric pattern is a subset of the 25 "invalid" patterns* or a superset of one of the 49 "valid" patterns.

Well done! A clever way to structure the set of 6016 ed-fully symmetric patterns.
* assuming your list of 25 invalids is correct.

Thanks! I think "25 invalid patterns list" is checked carefully enough - 3 persons (Afmob, blue and me) independently confirmed invalidity of those patterns.

Serg

[Edited. I corrected grammar mistake.]
Serg
2017 Supporter
 
Posts: 499
Joined: 01 June 2010
Location: Russia

Re: Fully symmetrical invalid patterns

Postby blue » Fri Mar 31, 2017 8:01 pm

Hi Afmob,

Afmob wrote:blue, your ED count for F11 with filtering is correct. It seems that I missed some a priori invalid puzzles in my first implementation. Nevertheless, the result of the first computation still holds since it didn't miss any (possible) valid puzzle.

That's good news. Thank you.

The last days I tried getting the number of ED valid puzzles of F78, which has 25 clues and 512 automorphisms, to see if it is feasible to get the valid puzzle count for all valid patterns with at least 24 clues.

...

The computation took about 2 days with 3 CPU cores with some breaks in between.

...

As you can see, we have a very small number of valid puzzles but a huge number of puzzles to be checked. So I think that with the current method, it is not feasible get the count for the other minimal valid patterns.

Yeah, I think that's right, unfortunately.
blue
 
Posts: 572
Joined: 11 March 2013

Re: Fully symmetrical invalid patterns

Postby blue » Fri Mar 31, 2017 10:09 pm

Hi Serg,

JPF wrote:
Serg wrote:So, I can state that every fully symmetric pattern is "subset" or "superset".

I checked and I can confirm your results:
Every fully symmetric pattern is a subset of the 25 "invalid" patterns* or a superset of one of the 49 "valid" patterns.

Well done! A clever way to structure the set of 6016 ed-fully symmetric patterns.

I had done that confirmation, too.

Serg wrote:
blue wrote:To avoid (possible) confusion in the future, it might be good to explain things in a little more depth.

I am ready to discuss this project in details (if there will be someone's interest).
blue wrote:Explain how these two (valid) puzzles, fit into your outline ...

Code: Select all
4 7 . | . . . | . 5 3
2 . 5 | . . . | 8 . 7
. 3 . | . . . | . 6 .
------+-------+------
. . . | 5 7 2 | . . .
. . . | 4 . 3 | . . .
. . . | 1 8 9 | . . .
------+-------+------
. 8 . | . . . | . 7 .
3 . 2 | . . . | 9 . 8
1 6 . | . . . | . 3 4

Your second example (cited above) is more complicated than the first one. But it is superset of F77 pattern. Swap columns c4/c5 of your example to detect that resulting pattern is superset of F77.


F77 too ... Interesting :!:
It wasn't as complicated as I thought.
I saw it as a "superset" (in quotes) of F55.
Swapping rows 2&3, rows 7&8, columns 1&2 and columns 8&9, shows the connection with F55.

The point that I was trying to bring out, about those two patterns, was that none of thier "actual" subsets, both 1) has a valid puzzle, and 2) is fully symmetric. Similarly, neither of them can be mapped to another form that 1) is fully symmetric, and 2) is an "actual" superset of one of the 49 "valid" shapes. On the other hand, each has at least one subset that 1) does have valid puzzles, 2) is not fully summetric 3) is, as it turns out, isomorphic to a fully symmetric pattern. Similarly (again), each one can be mapped to a form that 1) is not fully symmetric, but 2) is an "actual" superset of one of the 49 "valid" shapes.

The "(possible) confusion in the future", that I was worried about, involved the possiblity that someone might not understand that those kinds of details were in play.

Like JPF, I applaud your use of the 6106 "ED" shapes, and the corresponding interpretations for the "subset"/"superset" relations.
For fixing the "core" sets of 25 and 49 puzzle shapes, it's the best approach.
Also, your mention of a "magic-60" list, wouldn't be affected by the concerns that I mentioned.

---

As food for thought ... there is another way to look at things:

  1. There is a universe of "fully symmetric shapes", and corresponding puzzles (valid or not).
  2. There is a set of transformations ... a subset of the usual set of VPT's ... that includes only the transformations that map fully symmetric shapes (in general), to fully symmetric shapes. In particular, each one, maps every fully symmetric puzzle, to a fully symmetric puzzle, and (so) every fully symmetric shape, to a fully symmetric shape.
  3. For those transformations, a fully symmetric superset/subset, of a fully symmetric shape ... is always mapped to a fully symmetric subset/superset of the image of the initial shape.
  4. There is a corresponding notion of "ED"-vs-"EE", and/or "non-isomorphic"-vs-"isomorphic", for puzzles and/or shapes. Two puzzles/shapes are "isomorphic"/"EE", if and only if they are related by one of the transformations in (2). [ Note "EE", is short for "essentially equivalent". ]
  5. In that view:
    1. The number of "ED" shapes, is 6528 (rather than 6106).
    2. The number of "ED maximal invalid shapes", is 29 (rather than 25).
      Each "invalid" fully symmetric shape is an (actual) fully symmetric subset, of one of the shapes that is "EE" (in the restricted sense) to a shape from that list.
    3. The number of "ED minimal valid shapes", is 57 (rather than 49).
      Each "valid" fully symmetric shape is an (actual) fully symmetric superset, of one of the shapes that is "EE" (in the restricted sense) a shape from that list.

The 4 extra "maximal invalid" shapes, are due to pairs like these two, that are "EE" in the usual sense, but not "EE" in the restricted sense.

Code: Select all
        F7                   F7a

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

Note: The 2nd one has fully a fully symmetric superset, that (in the restricted sense) is not "EE/isomorphic" to any fully symmetric superset of the first shape. (Add r19c19 to the 2nd shape). That's meant to show that there's at least some reason to think that the shapes couldn't possibly be "essentially equivalent".

For the 8 extra "minimal valid" shapes, 4 of them are the "2nd half" of pairs like the one above.
The other 4 include the two that I mentioned earlier, and the shapes for these puzzles:

Code: Select all
. 7 3 | . . . | 5 9 .
8 . 5 | . . . | 7 . 4
2 4 . | . . . | . 8 3
------+-------+------
. . . | 7 . 4 | . . .
. . . | . 9 . | . . .
. . . | 5 . 2 | . . .
------+-------+------
9 2 . | . . . | . 4 6
1 . 6 | . . . | 9 . 7
. 3 4 | . . . | 1 2 .


. 9 2 | . . . | 8 1 .
1 . 3 | . . . | 4 . 7
6 7 . | . . . | . 3 2
------+-------+------
. . . | 1 7 4 | . . .
. . . | 6 . 8 | . . .
. . . | 2 5 3 | . . .
------+-------+------
7 6 . | . . . | . 8 3
3 . 1 | . . . | 2 . 9
. 2 9 | . . . | 6 7 .


Cheers,
Blue.
blue
 
Posts: 572
Joined: 11 March 2013

Re: Fully symmetrical invalid patterns

Postby JPF » Sun Apr 02, 2017 11:11 pm

The subgroup of transformations G acting on the set E of the 32768 fully symmetric patterns is of order 192 = 8 x 24
192 is a divisor of 2 x 6^8= 3359232 (Lagrange's theorem)
Two patterns P and Q of E are FS-equivalent* if there exists f ∈ G such that f(P) = Q.
If P and Q are not FS-equivalent, they are FS-ed
As blue wrote, there are 6528 FS-ed patterns.

Patterns have 32, 64 or 192 FS-automorphisms (including identity). Here are some examples:
Code: Select all
32  .............1.......1.1.....1...1...1.....1...1...1.....1.1.......1.............
64  1...1...1.11...11..11...11.....1....1..1.1..1....1.....11...11..11...11.1...1...1
192 111...111111...111111...111....1.......1.1.......1....111...111111...111111...111

Edit - Addition:
I just re-read this smart Ocean's postin the fully symmetrical puzzles thread
He analyzed the nature of the set G :
Ocean wrote:An attempt (reasoning, but no proof) ... :
Full symmetry is always preserved when (any combination of) this subset of the equivalence transformations is performed:
1. Simultaneous permutation of rows 1-3, rows 7-9, columns 1-3, columns 7-9. (Factor 6).
2. Turn the board upside down. (Factor 2).
3. Turn the board left-to-right. (Factor 2).
4. Switch rows 4 and 6. (Factor 2).
5. Switch columns 4 and 6. (Factor 2).
6. Turn the board 90 degrees (rows become columns). (Factor 2).
The factor 192 is the combination of all these (6*2^5=192).

I did a full analysis of the 2 x 6^8 transformations confirming his claim.
He added:
It should be noted that some specific patterns preserve full symmetry with other transformations as well. Therefore care has to be taken before concluding that checking these 192 variations guarantees isomorphism. It's not valid for all patterns.
Other transformations than those listed may be chosen as a basis, but they can be expressed a combination of those listed (and vice versa). The first transformation listed (#1) normally does not preserve the pattern, but serves as a normalization, catching 'equivalent patterns'

This point is not clear to me:
By definition, G is the restriction of the set all transformations to the fully symmetric patterns E
and then ∀ f ∈ G and ∀ X ∈ E : f(X) ∈ E
Of course, we can find some f ∉ G such that for some X ∈ E (but not all ) f(X) ∈ E

JPF
* I use FS-equivalent to avoid confusion.
Last edited by JPF on Tue Apr 04, 2017 10:42 pm, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: Fully symmetrical invalid patterns

Postby Serg » Mon Apr 03, 2017 10:19 pm

Hi, blue!
blue wrote:
JPF wrote:
Serg wrote:So, I can state that every fully symmetric pattern is "subset" or "superset".

I checked and I can confirm your results:
Every fully symmetric pattern is a subset of the 25 "invalid" patterns* or a superset of one of the 49 "valid" patterns.

Well done! A clever way to structure the set of 6016 ed-fully symmetric patterns.

I had done that confirmation, too.

Thanks! Your confirmation is very important for me.

blue wrote:
Serg wrote:
blue wrote:Explain how these two (valid) puzzles, fit into your outline ...

Code: Select all
4 7 . | . . . | . 5 3
2 . 5 | . . . | 8 . 7
. 3 . | . . . | . 6 .
------+-------+------
. . . | 5 7 2 | . . .
. . . | 4 . 3 | . . .
. . . | 1 8 9 | . . .
------+-------+------
. 8 . | . . . | . 7 .
3 . 2 | . . . | 9 . 8
1 6 . | . . . | . 3 4

Your second example (cited above) is more complicated than the first one. But it is superset of F77 pattern. Swap columns c4/c5 of your example to detect that resulting pattern is superset of F77.


It wasn't as complicated as I thought.
I saw it as a "superset" (in quotes) of F55.
Swapping rows 2&3, rows 7&8, columns 1&2 and columns 8&9, shows the connection with F55.

This example looks like simple only when one knows the answer. Initially I tried to find superset valid pattern "by eye" - mainly trying to transform F55 pattern, but I didn't find your solution. So, when your brain doesn't work you have to use computer ... My filtering program said that your second example pattern is superset of F77 pattern. But having this hint I didn't still see solution. I decided, that my filtering program has a bug, and intended to search this bug, but at that moment I saw solution. So, my program was smarter than me :( .

blue wrote:The point that I was trying to bring out, about those two patterns, was that none of thier "actual" subsets, both 1) has a valid puzzle, and 2) is fully symmetric. Similarly, neither of them can be mapped to another form that 1) is fully symmetric, and 2) is an "actual" superset of one of the 49 "valid" shapes. On the other hand, each has at least one subset that 1) does have valid puzzles, 2) is not fully summetric 3) is, as it turns out, isomorphic to a fully symmetric pattern. Similarly (again), each one can be mapped to a form that 1) is not fully symmetric, but 2) is an "actual" superset of one of the 49 "valid" shapes.

It's rather complicated statement. I tried to follow it but crashed in "3)" point. You say about 2 your examples, right?
blue wrote:each has at least one subset that 1) does have valid puzzles, 2) is not fully summetric 3) is, as it turns out, isomorphic to a fully symmetric pattern.

Yes, both example patterns have subsets which have valid puzzles and are not fully symmetric. But why are those subsets isomorphic to a fully symmetric pattern? Those subsets are supersets for some valid fully symmetrical patterns from "49 patterns list" :?: .

blue wrote:As food for thought ... there is another way to look at things:

  1. There is a universe of "fully symmetric shapes", and corresponding puzzles (valid or not).
  2. There is a set of transformations ... a subset of the usual set of VPT's ... that includes only the transformations that map fully symmetric shapes (in general), to fully symmetric shapes. In particular, each one, maps every fully symmetric puzzle, to a fully symmetric puzzle, and (so) every fully symmetric shape, to a fully symmetric shape.
  3. For those transformations, a fully symmetric superset/subset, of a fully symmetric shape ... is always mapped to a fully symmetric subset/superset of the image of the initial shape.
  4. There is a corresponding notion of "ED"-vs-"EE", and/or "non-isomorphic"-vs-"isomorphic", for puzzles and/or shapes. Two puzzles/shapes are "isomorphic"/"EE", if and only if they are related by one of the transformations in (2). [ Note "EE", is short for "essentially equivalent". ]
  5. In that view:
    1. The number of "ED" shapes, is 6528 (rather than 6106).
    2. The number of "ED maximal invalid shapes", is 29 (rather than 25).
      Each "invalid" fully symmetric shape is an (actual) fully symmetric subset, of one of the shapes that is "EE" (in the restricted sense) to a shape from that list.
    3. The number of "ED minimal valid shapes", is 57 (rather than 49).
      Each "valid" fully symmetric shape is an (actual) fully symmetric superset, of one of the shapes that is "EE" (in the restricted sense) a shape from that list.

Interesting results, well done!

I tried to get mathematical way of calculation number of essentially different fully symmetrical sudoku patterns (6016), but unfortunately I was not succeed in doing this... yet.

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

Re: Fully symmetrical invalid patterns

Postby blue » Wed Apr 05, 2017 1:54 am

Hi Serg,

Serg wrote:
blue wrote:The point that I was trying to bring out, about those two patterns, was that none of thier "actual" subsets, both 1) has a valid puzzle, and 2) is fully symmetric. Similarly, neither of them can be mapped to another form that 1) is fully symmetric, and 2) is an "actual" superset of one of the 49 "valid" shapes. On the other hand, each has at least one subset that 1) does have valid puzzles, 2) is not fully summetric 3) is, as it turns out, isomorphic to a fully symmetric pattern. Similarly (again), each one can be mapped to a form that 1) is not fully symmetric, but 2) is an "actual" superset of one of the 49 "valid" shapes.

It's rather complicated statement. I tried to follow it but crashed in "3)" point. You say about 2 your examples, right?
blue wrote:each has at least one subset that 1) does have valid puzzles, 2) is not fully summetric 3) is, as it turns out, isomorphic to a fully symmetric pattern.

Yes, both example patterns have subsets which have valid puzzles and are not fully symmetric. But why are those subsets isomorphic to a fully symmetric pattern? Those subsets are supersets for some valid fully symmetrical patterns from "49 patterns list" :?: .

There is no "why". It's just by chance (?), that such subsets do exist.
To answer the 2nd question: the subsets that I had in mind, were the ones that are actual isomorphs of "fully symmetrical patterns from '49 patterns list' ".

Looking at the first part of your last post, I'm not sure whether it was intentional or not, but you seem to have adopted the following definitions, for fully symmetric patterns:

  1. Pattern A is a "subset" of pattern B, if and only if pattern A is isomorphic to an actual subset ... symmetric or not ... of pattern B.
  2. Pattern A is a "superset" of pattern B, if and only if pattern B is a "subset" of pattern A (using the interpretation in (1)).
  3. A (symmetric) pattern is a "minimal/maximal (symmetric) pattern", satisfying some property, if and only if it satisfies the property, and using the interpretations in (1)/(2), none of its (symmetric) "supersets/subsets", satisfies the property.
Note: The definition in (1), is perfectly fine, in the sense that it satisfies: "A is a 'subset' of B, and B is a 'subset' of C" implies "A is a 'subset' of C".
In some way, that's related to your 2nd question, and my mention of "actual isomorphs" of patterns from the list of 49.

Note2: In (3), I took special care to not use the term(s) "symmetrically minimal/maximal".
At this point, and for whatever reasons ... agree or disagree, as you like ... they seem to be a bit ambiguous.
Also ... intentionally or not ... you didn't use those terms, in describing the lists of 25 and 49 patterns.

Cheers,
Blue.
blue
 
Posts: 572
Joined: 11 March 2013

Re: Fully symmetrical invalid patterns

Postby Serg » Thu Apr 06, 2017 5:23 pm

Hi, blue!
blue wrote:Looking at the first part of your last post, I'm not sure whether it was intentional or not, but you seem to have adopted the following definitions, for fully symmetric patterns:

  1. Pattern A is a "subset" of pattern B, if and only if pattern A is isomorphic to an actual subset ... symmetric or not ... of pattern B.
  2. Pattern A is a "superset" of pattern B, if and only if pattern B is a "subset" of pattern A (using the interpretation in (1)).
  3. A (symmetric) pattern is a "minimal/maximal (symmetric) pattern", satisfying some property, if and only if it satisfies the property, and using the interpretations in (1)/(2), none of its (symmetric) "supersets/subsets", satisfies the property.

Yes, I meant exactly this sense of terms "subset"/"superset". Your definitions are correct. Maybe it would be better to use terms "isomorphic subset" and "isomorphic superset" instead of "subset"/"superset" in double quotes. I intentionally avoided new terms creation, but it is evident that new terms must be used in this case.
blue wrote:Note2: In (3), I took special care to not use the term(s) "symmetrically minimal/maximal".
At this point, and for whatever reasons ... agree or disagree, as you like ... they seem to be a bit ambiguous.
Also ... intentionally or not ... you didn't use those terms, in describing the lists of 25 and 49 patterns.

I intentionally avoided the terms "symmetrically minimal/maximal" usage, because many readers of this thread are not familar with "minimal" and "maximal" patterns terminology. But we should choose a definition for such "constrainted" minimality/maximality. I propose 2 variants for such patterns property:

1. "constraintly minimal (maximal) pattern" in opposite to simply "minimal (maximal) pattern".
2. "weakly minimal (maximal) pattern" in opposite to "strongly minimal (maximal) pattern" or simply "minimal (maximal) pattern".

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

Previous

Return to General