Anticorner maximal invalid patterns
Re: Anticorner maximal invalid patterns
by JPF » Sun Jun 09, 2024 2:08 pm
deleted
Last edited by JPF on Sun Jun 09, 2024 5:03 pm, edited 1 time in total.
- JPF
- 2017 Supporter
- Posts: 6139
- Joined: 06 December 2005
- Location: Paris, France
Re: Anticorner maximal invalid patterns
by Serg » Sun Jun 09, 2024 3:04 pm
Hi, JPF!
Please describe permutations group you used in readable for humans form.
Serg
Please describe permutations group you used in readable for humans form.
Serg
- Serg
- 2018 Supporter
- Posts: 889
- Joined: 01 June 2010
- Location: Russia
Re: Anticorner maximal invalid patterns
by blue » Sun Jun 09, 2024 6:46 pm
Hi Serg,
I didn't account for them, and for verification purposes I didn't want anyone else to either. It isn't compatible with the idea of having a *group* of transformations, any one of which can be applied to any pattern in the class, producing (always) another pattern in the class ... possobly the same pattern, but always a pattern in the class. If the "group" aspect was lost, things like Burnside's Lemma, wouldn't be applicable.
For something to do, I'll hack some code together to what you're suggesting, using "brute force".
It seems like the results would be very difficult to verify "by other means", though.
This would work for a set of generators:
1) swap rows 1 and 2
2) swap rows 1 and 3
3) swap rows 4 and 5
4) swap rows 4 and 6
5) swap rows 7 and 8
6) swap rows 7 and 9
7) diagonal reflection (the one that maps the r1c1-r9c9 diagonal to itself).
Best regards,
Blue.
Serg wrote:Did you account for bands/stacks permutations? Some anticorner patterns having more than 3 filled boxes permit bands/stacks permutations.
I didn't account for them, and for verification purposes I didn't want anyone else to either. It isn't compatible with the idea of having a *group* of transformations, any one of which can be applied to any pattern in the class, producing (always) another pattern in the class ... possobly the same pattern, but always a pattern in the class. If the "group" aspect was lost, things like Burnside's Lemma, wouldn't be applicable.
For something to do, I'll hack some code together to what you're suggesting, using "brute force".
It seems like the results would be very difficult to verify "by other means", though.
Serg wrote:Hi, JPF!
Please describe permutations group you used in readable for humans form.
This would work for a set of generators:
1) swap rows 1 and 2
2) swap rows 1 and 3
3) swap rows 4 and 5
4) swap rows 4 and 6
5) swap rows 7 and 8
6) swap rows 7 and 9
7) diagonal reflection (the one that maps the r1c1-r9c9 diagonal to itself).
Best regards,
Blue.
- blue
- Posts: 1013
- Joined: 11 March 2013
Re: Anticorner maximal invalid patterns
by Serg » Sun Jun 09, 2024 8:21 pm
Hi, Blue!
I agree with you. I am sure VPT preserving anticorner form (B6, B8 and B9 boxes contain 9 clues each) don't form a group, so Burnside Lemma cannot be applied in this case. (The situation resembles fully symmetrical patterns case, when 6016 ED patterns came from brute force search, not from combinatorics tools.)
It's interesting what will you get. I cannot create a program with acceptable performance yet. Anyway it's a toy. I think it cannot provide any verification.
I don't understand this description. Does it relate to VPT preserving anticorner form?
Serg
blue wrote:Serg wrote:Did you account for bands/stacks permutations? Some anticorner patterns having more than 3 filled boxes permit bands/stacks permutations.
I didn't account for them, and for verification purposes I didn't want anyone else to either. It isn't compatible with the idea of having a *group* of transformations, any one of which can be applied to any pattern in the class, producing (always) another pattern in the class ... possobly the same pattern, but always a pattern in the class. If the "group" aspect was lost, things like Burnside's Lemma, wouldn't be applicable.
I agree with you. I am sure VPT preserving anticorner form (B6, B8 and B9 boxes contain 9 clues each) don't form a group, so Burnside Lemma cannot be applied in this case. (The situation resembles fully symmetrical patterns case, when 6016 ED patterns came from brute force search, not from combinatorics tools.)
blue wrote:For something to do, I'll hack some code together to what you're suggesting, using "brute force".
It seems like the results would be very difficult to verify "by other means", though.
It's interesting what will you get. I cannot create a program with acceptable performance yet. Anyway it's a toy. I think it cannot provide any verification.
Serg wrote:Hi, JPF!
Please describe permutations group you used in readable for humans form.
blue wrote:This would work for a set of generators:
1) swap rows 1 and 2
2) swap rows 1 and 3
3) swap rows 4 and 5
4) swap rows 4 and 6
5) swap rows 7 and 8
6) swap rows 7 and 9
7) diagonal reflection (the one that maps the r1c1-r9c9 diagonal to itself).
I don't understand this description. Does it relate to VPT preserving anticorner form?
Serg
- Serg
- 2018 Supporter
- Posts: 889
- Joined: 01 June 2010
- Location: Russia
Re: Anticorner maximal invalid patterns
by blue » Sun Jun 09, 2024 9:52 pm
Hi Serg,
It does form a group. It's just the automorphism group for the pattern with B689 full and everything else empty.
I understand what you're getting at, and that it's similar to the situation here.
The set of VPT's that maps *every* fully symmetric pattern to a fully symmetric pattern, does form a group, though, and the set of fully symmetric patterns partitions into a set of orbits under that group. As you suggest, there are more than 6016 orbits. What ever the count is, if we choose one pattern from each orbit, we can say that the patterns are ED with respect to that group, since no two of them are related by a member of the group.
What brings the ("true ED ?") count down to 6016, is the fact that sometimes a pattern in one orbit is isomorphic to a pattern in a differernt orbit, but only via a VPT that isn't in the group -- one that maps at least one fully symmetric pattern to a non-fully-symmetric pattern.
Yes. If you like, it's a set of generators for the automorphism group for the B689 pattern.
--------
Preliminary results suggest that the total pattern count will be smaller by ~ 1.4%, with the count for size 27 smaller by ~0.7%.
Serg wrote:I am sure VPT preserving anticorner form (B6, B8 and B9 boxes contain 9 clues each) don't form a group (...)
It does form a group. It's just the automorphism group for the pattern with B689 full and everything else empty.
The situation resembles fully symmetrical patterns case, when 6016 ED patterns came from brute force search, not from combinatorics tools.
I understand what you're getting at, and that it's similar to the situation here.
The set of VPT's that maps *every* fully symmetric pattern to a fully symmetric pattern, does form a group, though, and the set of fully symmetric patterns partitions into a set of orbits under that group. As you suggest, there are more than 6016 orbits. What ever the count is, if we choose one pattern from each orbit, we can say that the patterns are ED with respect to that group, since no two of them are related by a member of the group.
What brings the ("true ED ?") count down to 6016, is the fact that sometimes a pattern in one orbit is isomorphic to a pattern in a differernt orbit, but only via a VPT that isn't in the group -- one that maps at least one fully symmetric pattern to a non-fully-symmetric pattern.
Serg wrote:Hi, JPF!
Please describe permutations group you used in readable for humans form.blue wrote:This would work for a set of generators:
1) swap rows 1 and 2
2) swap rows 1 and 3
3) swap rows 4 and 5
4) swap rows 4 and 6
5) swap rows 7 and 8
6) swap rows 7 and 9
7) diagonal reflection (the one that maps the r1c1-r9c9 diagonal to itself).
I don't understand this description. Does it relate to VPT preserving anticorner form?
Yes. If you like, it's a set of generators for the automorphism group for the B689 pattern.
--------
blue wrote:For something to do, I'll hack some code together to what you're suggesting, using "brute force".
It seems like the results would be very difficult to verify "by other means", though.
It's interesting what will you get.
Preliminary results suggest that the total pattern count will be smaller by ~ 1.4%, with the count for size 27 smaller by ~0.7%.
- blue
- Posts: 1013
- Joined: 11 March 2013
Re: Anticorner maximal invalid patterns
by JPF » Sun Jun 09, 2024 10:12 pm
I understand Serg's concern, but on the other hand, by using a "certain method", I was able to find Blue's numbers.
I revisited my old programs that I had used for counting patterns in cases of empty Boxes.
The results are here and, to my knowledge, they are correct.
Here is how the process unfolds:
Ignore the cells of boxes 6, 8, and 9 and renumber the remaining cells from 1 to 54.
Define a permutation group for the remaining cells as follows:
This group was perfectly defined in terms of cycle products and in GAP format, as is customary in this field...
I then apply to this group the method explained here, adapting it to its own characteristics (number of clues, size, conjugacy classes), and by applying Burnside's lemma... and it works!
and I must admit that I am not able to say precisely why.
JPF
I revisited my old programs that I had used for counting patterns in cases of empty Boxes.
The results are here and, to my knowledge, they are correct.
Here is how the process unfolds:
Ignore the cells of boxes 6, 8, and 9 and renumber the remaining cells from 1 to 54.
Define a permutation group for the remaining cells as follows:
- * Permutation of the first three rows (over 9 cells)
* Permutation of the next 3 rows over 6 cells
* Permutation of the next 3 rows over 3 cells
* Permutation of the first three columns (over 9 cells)
* Permutation of the next 3 columns over 6 cells
* Permutation of the next 3 columns over 3 cells
* Finally, apply a reflection (54 cells)
This group was perfectly defined in terms of cycle products and in GAP format, as is customary in this field...
I then apply to this group the method explained here, adapting it to its own characteristics (number of clues, size, conjugacy classes), and by applying Burnside's lemma... and it works!
and I must admit that I am not able to say precisely why.
JPF
- JPF
- 2017 Supporter
- Posts: 6139
- Joined: 06 December 2005
- Location: Paris, France
Re: Anticorner maximal invalid patterns
by Serg » Sun Jun 09, 2024 11:30 pm
Hi, Blue, JPF!
Please, answer - are anticorner patterns A and B equivalent or not?
Serg
Please, answer - are anticorner patterns A and B equivalent or not?
- Code: Select all
A B
+-----+-----+-----+ +-----+-----+-----+
|. . .|. . .|. . .| |. . .|. . .|. . .|
|. . .|. . .|. . x| |. . .|. . .|. . x|
|. . x|. . .|. . .| |. . .|. . x|. . .|
+-----+-----+-----+ +-----+-----+-----+
|. . .|x x x|x x x| |x x x|. . .|x x x|
|. . .|x x x|x x x| |x x x|. . .|x x x|
|x x x|x x x|x x x| |x x x|x x x|x x x|
+-----+-----+-----+ +-----+-----+-----+
|x x x|x x x|x x x| |x x x|x x x|x x x|
|x x x|x x x|x x x| |x x x|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
- 2018 Supporter
- Posts: 889
- Joined: 01 June 2010
- Location: Russia
Re: Anticorner maximal invalid patterns
by blue » Mon Jun 10, 2024 1:58 am
Hi Serg,
Without a definition for what "equivalent" means, there's no good way to answer.
It's certainly true that one has puzzles, if and only if the other one does.
Added: On the other hand, there is no standard VPT that preserves the B689 (and B123457) shape(s), and maps pattern A to pattern B.
Let me ask another question. Consider these two patterns:
Both have puzzles.
The one on the right, has the property that 4 clues can be removed from the B123457 region, leaving a pattern that still has puzzles.
The one on the left, doesn''t have that property.
Does that mean they are "not equivalent" ?
Serg wrote:Please, answer - are anticorner patterns A and B equivalent or not?
Without a definition for what "equivalent" means, there's no good way to answer.
It's certainly true that one has puzzles, if and only if the other one does.
Added: On the other hand, there is no standard VPT that preserves the B689 (and B123457) shape(s), and maps pattern A to pattern B.
Let me ask another question. Consider these two patterns:
- 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|
+-----+-----+-----+ +-----+-----+-----+
Both have puzzles.
The one on the right, has the property that 4 clues can be removed from the B123457 region, leaving a pattern that still has puzzles.
The one on the left, doesn''t have that property.
Does that mean they are "not equivalent" ?
- blue
- Posts: 1013
- Joined: 11 March 2013
Re: Anticorner maximal invalid patterns
by blue » Mon Jun 10, 2024 2:21 pm
JPF wrote:I understand Serg's concern, but on the other hand, by using a "certain method", I was able to find Blue's numbers.
I revisited my old programs that I had used for counting patterns in cases of empty Boxes.
The results are here and, to my knowledge, they are correct.
The first two rows are:
- Code: Select all
n B1 B1B2 B1B2B3 B1B2B3B4 B1B2B3B4B5 B1B2B3B4B5B6 B1B2B3B4B5B6B7 B1B2B3B4B5B6B7B8 B1B2B3B4B5B6B7B8B9
0 1 1 1 1 1 1 1 1 1
1 1 1 1 3 3 1 3 2 1
Regarding Serg's concern: B1B2B3B4 is listed as having 3 "non-equivalent" 1-clue patterns.
Three is correct, in the sense that the clue can be in B1, in B4, or in one of {B2,B3}.
Isn't there really only one "ED" 1-clue pattern, though ?
Food for thought:
- Code: Select all
+-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+
|. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . .|. . .|
|. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . .|. . .|
|. . 1|. . .|. . .| |. . .|. . .|. . 1| |. . .|. . .|. . .|
+-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+
|. . .|2 2 2|2 2 2| |. . .|2 2 2|2 2 2| |. . .|2 2 2|2 2 2|
|. . .|2 2 2|2 2 2| |. . .|2 2 2|2 2 2| |. . .|2 2 2|2 2 2|
|. . .|2 2 2|2 2 2| |. . .|2 2 2|2 2 2| |. . 1|2 2 2|2 2 2|
+-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+
|2 2 2|2 2 2|2 2 2| |2 2 2|2 2 2|2 2 2| |2 2 2|2 2 2|2 2 2|
|2 2 2|2 2 2|2 2 2| |2 2 2|2 2 2|2 2 2| |2 2 2|2 2 2|2 2 2|
|2 2 2|2 2 2|2 2 2| |2 2 2|2 2 2|2 2 2| |2 2 2|2 2 2|2 2 2|
+-----+-----+-----+ +-----+-----+-----+ +-----+-----+-----+
- blue
- Posts: 1013
- Joined: 11 March 2013
Re: Anticorner maximal invalid patterns
by blue » Mon Jun 10, 2024 3:31 pm
blue wrote:Hi Serg,Serg wrote:Did you account for bands/stacks permutations? Some anticorner patterns having more than 3 filled boxes permit bands/stacks permutations.
I didn't account for them, and for verification purposes I didn't want anyone else to either. It isn't compatible with the idea of having a *group* of transformations, any one of which can be applied to any pattern in the class, producing (always) another pattern in the class ... possobly the same pattern, but always a pattern in the class. If the "group" aspect was lost, things like Burnside's Lemma, wouldn't be applicable.
For something to do, I'll hack some code together to what you're suggesting, using "brute force".
It seems like the results would be very difficult to verify "by other means", though.
That's done.
FWIW (... not much), here's a table from before (left), with the new results on the right.
- Code: Select all
original better?
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
| | ED shapes V1 | with puzzles | without | | | ED shapes V2 | with puzzles | without |
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
| 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 1 |
| 1 | 4 | 0 | 4 | | 1 | 4 | 0 | 4 |
| 2 | 23 | 0 | 23 | | 2 | 23 | 0 | 23 |
| 3 | 125 | 0 | 125 | | 3 | 125 | 0 | 125 |
| 4 | 630 | 0 | 630 | | 4 | 630 | 0 | 630 |
| 5 | 2970 | 0 | 2970 | | 5 | 2970 | 0 | 2970 |
| 6 | 13089 | 322 | 12767 | | 6 | 13089 | 322 | 12767 |
| 7 | 53801 | 7931 | 45870 | | 7 | 53801 | 7931 | 45870 |
| 8 | 206531 | 67945 | 138586 | | 8 | 206531 | 67945 | 138586 |
| 9 | 739539 | 376905 | 362634 | | 9 | 739539 | 376905 | 362634 |
| 10 | 2468234 | 1637582 | 830652 | <----> | 10 | 2468229 | 1637582 | 830647 |
| 11 | 7674378 | 6000606 | 1673772 | | 11 | 7674347 | 6000606 | 1673741 |
| 12 | 22221573 | 19242693 | 2978880 | | 12 | 22221385 | 19242689 | 2978696 |
| 13 | 59917001 | 55207479 | 4709522 | | 13 | 59916125 | 55207371 | 4708754 |
| 14 | 150468286 | 143809400 | 6658886 | | 14 | 150464473 | 143808203 | 6656270 |
| 15 | 352048728 | 343570837 | 8477891 | | 15 | 352033927 | 343563329 | 8470598 |
| 16 | 767736056 | 757955049 | 9781007 | | 16 | 767683088 | 757919054 | 9764034 |
| 17 | 1561293914 | 1551012712 | 10281202 | | 17 | 1561120202 | 1550872236 | 10247966 |
| 18 | 2962363840 | 2952476453 | 9887387 | | 18 | 2961837605 | 2952006170 | 9831435 |
| 19 | 5246685692 | 5237962077 | 8723615 | | 19 | 5245216646 | 5236574793 | 8641853 |
| 20 | 8678086628 | 8671014152 | 7072476 | | 20 | 8674297755 | 8667330414 | 6967341 |
| 21 | 13410257969 | 13404986567 | 5271402 | | 21 | 13401236639 | 13396085176 | 5151463 |
| 22 | 19368071661 | 19364460624 | 3611037 | | 22 | 19348228004 | 19344738996 | 3489008 |
| 23 | 26152415035 | 26150143201 | 2271834 | | 23 | 26112099528 | 26109939088 | 2160440 |
| 24 | 33024031396 | 33022720219 | 1311177 | | 24 | 32948357572 | 32947137699 | 1219873 |
| 25 | 39006180915 | 39005487792 | 693123 | | 25 | 38874953598 | 38874327777 | 625821 |
| 26 | 43101117092 | 43100781986 | 335106 | | 26 | 42890840988 | 42890550427 | 290561 |
| 27 | 44559029938 | 44558881961 | 147977 | | 27 | 44247666508 | 44247545071 | 121437 |
| 28 | 43101117092 | 43101057515 | 59577 | | 28 | 42675009706 | 42674964222 | 45484 |
| 29 | 39006180915 | 39006159070 | 21845 | | 29 | 38467196682 | 38467181531 | 15151 |
| 30 | 33024031396 | 33024024108 | 7288 | | 30 | 32393841394 | 32393836900 | 4494 |
| 31 | 26152415035 | 26152412831 | 2204 | | 31 | 25471325435 | 25471324266 | 1169 |
| 32 | 19368071661 | 19368071057 | 604 | | 32 | 18687691195 | 18687690917 | 278 |
| 33 | 13410257969 | 13410257820 | 149 | | 33 | 12782123641 | 12782123583 | 58 |
| 34 | 8678086628 | 8678086596 | 32 | | 34 | 8142282288 | 8142282275 | 13 |
| 35 | 5246685692 | 5246685686 | 6 | | 35 | 4824527406 | 4824527404 | 2 |
| 36 | 2962363840 | 2962363839 | 1 | | 36 | 2655266711 | 2655266710 | 1 |
| 37 | 1561293914 | 1561293914 | 0 | | 37 | 1355139262 | 1355139262 | 0 |
| 38 | 767736056 | 767736056 | 0 | | 38 | 640103211 | 640103211 | 0 |
| 39 | 352048728 | 352048728 | 0 | | 39 | 279219005 | 279219005 | 0 |
| 40 | 150468286 | 150468286 | 0 | | 40 | 112196123 | 112196123 | 0 |
| 41 | 59917001 | 59917001 | 0 | | 41 | 41408584 | 41408584 | 0 |
| 42 | 22221573 | 22221573 | 0 | | 42 | 13993227 | 13993227 | 0 |
| 43 | 7674378 | 7674378 | 0 | | 43 | 4314111 | 4314111 | 0 |
| 44 | 2468234 | 2468234 | 0 | | 44 | 1209653 | 1209653 | 0 |
| 45 | 739539 | 739539 | 0 | | 45 | 307419 | 307419 | 0 |
| 46 | 206531 | 206531 | 0 | | 46 | 70934 | 70934 | 0 |
| 47 | 53801 | 53801 | 0 | | 47 | 14873 | 14873 | 0 |
| 48 | 13089 | 13089 | 0 | | 48 | 2929 | 2929 | 0 |
| 49 | 2970 | 2970 | 0 | | 49 | 542 | 542 | 0 |
| 50 | 630 | 630 | 0 | | 50 | 109 | 109 | 0 |
| 51 | 125 | 125 | 0 | | 51 | 21 | 21 | 0 |
| 52 | 23 | 23 | 0 | | 52 | 5 | 5 | 0 |
| 53 | 4 | 4 | 0 | | 53 | 1 | 1 | 0 |
| 54 | 1 | 1 | 0 | | 54 | 1 | 1 | 0 |
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
| | 432307140160 | | | | | 426176577800 | | |
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
- blue
- Posts: 1013
- Joined: 11 March 2013
Re: Anticorner maximal invalid patterns
by JPF » Mon Jun 10, 2024 4:52 pm
Hmm... I am getting more and more confused 
after these last posts. I am going to give myself some time to think about all these questions and possibly revise my calculations.
JPF
after these last posts. I am going to give myself some time to think about all these questions and possibly revise my calculations.JPF
- JPF
- 2017 Supporter
- Posts: 6139
- Joined: 06 December 2005
- Location: Paris, France
Re: Anticorner maximal invalid patterns
by blue » Mon Jun 10, 2024 7:12 pm
Hi JPF,
I hope you won't trash anything in that thread.
I truly admire your method & results.
You could add a note explaining that the patterns should be thought of as "non-equivalent x's and o's patterns" (that fill the specified boxes).
Then a (forward) link to a subsequent discussion of the issues, might be in order.
Blue.
P.S.: Besides, I'ld hate to think of these two as being "equivalent" B1B2 patterns
I hope you won't trash anything in that thread.
I truly admire your method & results.
You could add a note explaining that the patterns should be thought of as "non-equivalent x's and o's patterns" (that fill the specified boxes).
Then a (forward) link to a subsequent discussion of the issues, might be in order.
Blue.
P.S.: Besides, I'ld hate to think of these two as being "equivalent" B1B2 patterns
- Code: Select all
+-------+-------+
| x x x | . . . |
| . . . | . . . |
| . . . | . . . |
+-------+-------+
+-------+-------+
| x . . | . . . |
| x . . | . . . |
| x . . | . . . |
+-------+-------+
- blue
- Posts: 1013
- Joined: 11 March 2013
Re: Anticorner maximal invalid patterns
by Serg » Mon Jun 10, 2024 8:53 pm
Hi, Blue!
I am too late with my answers, but nevertheless ...
Yes, we study patterns validity in this thread. So, 2 patterns are equivalent (both are valid or both are invalid) if the first pattern can be transformed to the second pattern by some VPT provided that B6, B8 and B9 boxes remain filled after transformation.
You chose exotic property, but I talk about "patterns validity" property. Validity Preserving Transformation just preserves validity of puzzles/patterns.
Serg
I am too late with my answers, but nevertheless ...
blue wrote:Serg wrote:Please, answer - are anticorner patterns A and B equivalent or not?
Without a definition for what "equivalent" means, there's no good way to answer.
It's certainly true that one has puzzles, if and only if the other one does.
Yes, we study patterns validity in this thread. So, 2 patterns are equivalent (both are valid or both are invalid) if the first pattern can be transformed to the second pattern by some VPT provided that B6, B8 and B9 boxes remain filled after transformation.
blue wrote:Let me ask another question. Consider these two patterns:
- 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|
+-----+-----+-----+ +-----+-----+-----+
Both have puzzles.
The one on the right, has the property that 4 clues can be removed from the B123457 region, leaving a pattern that still has puzzles.
The one on the left, doesn''t have that property.
Does that mean they are "not equivalent" ?
You chose exotic property, but I talk about "patterns validity" property. Validity Preserving Transformation just preserves validity of puzzles/patterns.
Serg
- Serg
- 2018 Supporter
- Posts: 889
- Joined: 01 June 2010
- Location: Russia
Re: Anticorner maximal invalid patterns
by Serg » Mon Jun 10, 2024 9:19 pm
Hi, Blue!
Excellent! Right table looks like correct. There are 4 ED patterns with 53 clues in B123457 (one "hole" per grid) on the left table (band/stack permutatitions are prohibited) and there is 1 ED pattern with 53 clues on the right table (band/stack permutations are permitted). That's how it should be. Numbers for 35-clue invalid patterns look like correct too (6 ED patterns - 2 ED patterns).
It is curious that the left and right sums differ quite noticeably. (I expected to see fractions of percent difference.)
It’s simply incredible how you managed to remake your program and enumerate the patterns in a new way so fast!
Serg
blue wrote:blue wrote:That's done.
FWIW (... not much), here's a table from before (left), with the new results on the right.
- Code: Select all
original better?
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
| | ED shapes V1 | with puzzles | without | | | ED shapes V2 | with puzzles | without |
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
| 0 | 1 | 0 | 1 | | 0 | 1 | 0 | 1 |
| 1 | 4 | 0 | 4 | | 1 | 4 | 0 | 4 |
| 2 | 23 | 0 | 23 | | 2 | 23 | 0 | 23 |
| 3 | 125 | 0 | 125 | | 3 | 125 | 0 | 125 |
| 4 | 630 | 0 | 630 | | 4 | 630 | 0 | 630 |
| 5 | 2970 | 0 | 2970 | | 5 | 2970 | 0 | 2970 |
| 6 | 13089 | 322 | 12767 | | 6 | 13089 | 322 | 12767 |
| 7 | 53801 | 7931 | 45870 | | 7 | 53801 | 7931 | 45870 |
| 8 | 206531 | 67945 | 138586 | | 8 | 206531 | 67945 | 138586 |
| 9 | 739539 | 376905 | 362634 | | 9 | 739539 | 376905 | 362634 |
| 10 | 2468234 | 1637582 | 830652 | <----> | 10 | 2468229 | 1637582 | 830647 |
| 11 | 7674378 | 6000606 | 1673772 | | 11 | 7674347 | 6000606 | 1673741 |
| 12 | 22221573 | 19242693 | 2978880 | | 12 | 22221385 | 19242689 | 2978696 |
| 13 | 59917001 | 55207479 | 4709522 | | 13 | 59916125 | 55207371 | 4708754 |
| 14 | 150468286 | 143809400 | 6658886 | | 14 | 150464473 | 143808203 | 6656270 |
| 15 | 352048728 | 343570837 | 8477891 | | 15 | 352033927 | 343563329 | 8470598 |
| 16 | 767736056 | 757955049 | 9781007 | | 16 | 767683088 | 757919054 | 9764034 |
| 17 | 1561293914 | 1551012712 | 10281202 | | 17 | 1561120202 | 1550872236 | 10247966 |
| 18 | 2962363840 | 2952476453 | 9887387 | | 18 | 2961837605 | 2952006170 | 9831435 |
| 19 | 5246685692 | 5237962077 | 8723615 | | 19 | 5245216646 | 5236574793 | 8641853 |
| 20 | 8678086628 | 8671014152 | 7072476 | | 20 | 8674297755 | 8667330414 | 6967341 |
| 21 | 13410257969 | 13404986567 | 5271402 | | 21 | 13401236639 | 13396085176 | 5151463 |
| 22 | 19368071661 | 19364460624 | 3611037 | | 22 | 19348228004 | 19344738996 | 3489008 |
| 23 | 26152415035 | 26150143201 | 2271834 | | 23 | 26112099528 | 26109939088 | 2160440 |
| 24 | 33024031396 | 33022720219 | 1311177 | | 24 | 32948357572 | 32947137699 | 1219873 |
| 25 | 39006180915 | 39005487792 | 693123 | | 25 | 38874953598 | 38874327777 | 625821 |
| 26 | 43101117092 | 43100781986 | 335106 | | 26 | 42890840988 | 42890550427 | 290561 |
| 27 | 44559029938 | 44558881961 | 147977 | | 27 | 44247666508 | 44247545071 | 121437 |
| 28 | 43101117092 | 43101057515 | 59577 | | 28 | 42675009706 | 42674964222 | 45484 |
| 29 | 39006180915 | 39006159070 | 21845 | | 29 | 38467196682 | 38467181531 | 15151 |
| 30 | 33024031396 | 33024024108 | 7288 | | 30 | 32393841394 | 32393836900 | 4494 |
| 31 | 26152415035 | 26152412831 | 2204 | | 31 | 25471325435 | 25471324266 | 1169 |
| 32 | 19368071661 | 19368071057 | 604 | | 32 | 18687691195 | 18687690917 | 278 |
| 33 | 13410257969 | 13410257820 | 149 | | 33 | 12782123641 | 12782123583 | 58 |
| 34 | 8678086628 | 8678086596 | 32 | | 34 | 8142282288 | 8142282275 | 13 |
| 35 | 5246685692 | 5246685686 | 6 | | 35 | 4824527406 | 4824527404 | 2 |
| 36 | 2962363840 | 2962363839 | 1 | | 36 | 2655266711 | 2655266710 | 1 |
| 37 | 1561293914 | 1561293914 | 0 | | 37 | 1355139262 | 1355139262 | 0 |
| 38 | 767736056 | 767736056 | 0 | | 38 | 640103211 | 640103211 | 0 |
| 39 | 352048728 | 352048728 | 0 | | 39 | 279219005 | 279219005 | 0 |
| 40 | 150468286 | 150468286 | 0 | | 40 | 112196123 | 112196123 | 0 |
| 41 | 59917001 | 59917001 | 0 | | 41 | 41408584 | 41408584 | 0 |
| 42 | 22221573 | 22221573 | 0 | | 42 | 13993227 | 13993227 | 0 |
| 43 | 7674378 | 7674378 | 0 | | 43 | 4314111 | 4314111 | 0 |
| 44 | 2468234 | 2468234 | 0 | | 44 | 1209653 | 1209653 | 0 |
| 45 | 739539 | 739539 | 0 | | 45 | 307419 | 307419 | 0 |
| 46 | 206531 | 206531 | 0 | | 46 | 70934 | 70934 | 0 |
| 47 | 53801 | 53801 | 0 | | 47 | 14873 | 14873 | 0 |
| 48 | 13089 | 13089 | 0 | | 48 | 2929 | 2929 | 0 |
| 49 | 2970 | 2970 | 0 | | 49 | 542 | 542 | 0 |
| 50 | 630 | 630 | 0 | | 50 | 109 | 109 | 0 |
| 51 | 125 | 125 | 0 | | 51 | 21 | 21 | 0 |
| 52 | 23 | 23 | 0 | | 52 | 5 | 5 | 0 |
| 53 | 4 | 4 | 0 | | 53 | 1 | 1 | 0 |
| 54 | 1 | 1 | 0 | | 54 | 1 | 1 | 0 |
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
| | 432307140160 | | | | | 426176577800 | | |
+----+--------------+--------------+----------+ +----+--------------+--------------+----------+
Excellent! Right table looks like correct. There are 4 ED patterns with 53 clues in B123457 (one "hole" per grid) on the left table (band/stack permutatitions are prohibited) and there is 1 ED pattern with 53 clues on the right table (band/stack permutations are permitted). That's how it should be. Numbers for 35-clue invalid patterns look like correct too (6 ED patterns - 2 ED patterns).
It is curious that the left and right sums differ quite noticeably. (I expected to see fractions of percent difference.)
It’s simply incredible how you managed to remake your program and enumerate the patterns in a new way so fast!
Serg
- Serg
- 2018 Supporter
- Posts: 889
- Joined: 01 June 2010
- Location: Russia
Re: Anticorner maximal invalid patterns
by Serg » Tue Jun 11, 2024 4:07 pm
Hi!
I think Burnside's Lemma can still be used for anticorner patterns enumeration, but one must consider several cases (families) of anticorner patterns.
To get ED anticorner patterns number one should compute numbers of ED patterns for each case and then sum them.
Serg
[Edited. I put disclamer "don't use this method" because described method is raw and wasn't proved in any way.]
I think Burnside's Lemma can still be used for anticorner patterns enumeration, but one must consider several cases (families) of anticorner patterns.
- Code: Select all
****************************************************************************
* *
* Under construction! Don't use this method for practical purposes *
* *
****************************************************************************
Case 1
. . .
. . x
. x x
Boxes with 9 clues marked by "x", boxes with 0-8 clues marked by ".".
All different patterns: 511^6
Permitted VPTs:
1. Transposing - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting rows in band3 - 6 ways.
5. Permutting columns in stack1 - 6 ways.
6. Permutting columns in stack2 - 6 ways.
7. Permutting columns in stack3 - 6 ways.
Case 2
. . .
. . x
x x x
All different patterns: 511^5
Permitted VPTs:
1. Swapping stack1/stack2 - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting columns in stack1 - 6 ways.
5. Permutting columns in stack2 - 6 ways.
6. Permutting columns in stack3 - 6 ways.
Case 3
. . .
. x x
. x x
All different patterns: 511^5
Permitted VPTs:
1. Transposing - 2 ways.
2. Swapping band2/band3 - 2 ways.
3. Swapping stack2/stack3 - 2 ways.
4. Permutting rows in band1 - 6 ways.
5. Permutting rows in band2 - 6 ways.
6. Permutting rows in band3 - 6 ways.
7. Permutting columns in stack1 - 6 ways.
8. Permutting columns in stack2 - 6 ways.
9. Permutting columns in stack3 - 6 ways.
Case 4
. . .
. x x
x x x
All different patterns: 511^4
Permitted VPTs:
1. Swapping stack2/stack3 - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting columns in stack1 - 6 ways.
5. Permutting columns in stack2 - 6 ways.
6. Permutting columns in stack3 - 6 ways.
Case 5
. . .
x . x
. x x
All different patterns: 511^5
Permitted VPTs:
1. Swapping band2/band3 and stack1/stack2 - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting rows in band3 - 6 ways.
5. Permutting columns in stack1 - 6 ways.
6. Permutting columns in stack2 - 6 ways.
7. Permutting columns in stack3 - 6 ways.
Case 6
. . .
x x x
x x x
All different patterns: 511^3
Permitted VPTs:
1. Permutting rows in band1 - 6 ways.
2. Permutting columns in stack1 - 6 ways.
3. Permutting columns in stack2 - 6 ways.
4. Permutting columns in stack3 - 6 ways.
Case 7
. . x
. . x
x x x
All different patterns: 511^4
Permitted VPTs:
1. Transposing - 2 ways.
2. Swapping band1/band2 - 2 ways.
3. Swapping stack1/stack2 - 2 ways.
4. Permutting rows in band1 - 6 ways.
5. Permutting rows in band2 - 6 ways.
6. Permutting columns in stack1 - 6 ways.
7. Permutting columns in stack2 - 6 ways.
Case 8
. . x
. x x
x x x
All different patterns: 511^3
Permitted VPTs:
1. Transposing - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting columns in stack1 - 6 ways.
5. Permutting columns in stack2 - 6 ways.
Case 9
. . x
x x x
x x x
All different patterns: 511^2
Permitted VPTs:
1. Swapping stack1/stack2 - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting columns in stack1 - 6 ways.
4. Permutting columns in stack2 - 6 ways.
Case 10
. x .
. . x
x x x
All different patterns: 511^4
Permitted VPTs:
1. Swapping band1/band2 and stack2/stack3 - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting columns in stack1 - 6 ways.
5. Permutting columns in stack2 - 6 ways.
6. Permutting columns in stack3 - 6 ways.
Case 11
. x .
x . x
. x x
All different patterns: 511^4
Permitted VPTs:
1. Transposing - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting rows in band2 - 6 ways.
4. Permutting rows in band3 - 6 ways.
5. Permutting columns in stack1 - 6 ways.
6. Permutting columns in stack2 - 6 ways.
7. Permutting columns in stack3 - 6 ways.
Case 12
. x .
x . x
x x x
All different patterns: 511^3
Permitted VPTs:
1. Permutting rows in band1 - 6 ways.
2. Permutting rows in band2 - 6 ways.
3. Permutting columns in stack1 - 6 ways.
4. Permutting columns in stack2 - 6 ways.
5. Permutting columns in stack3 - 6 ways.
Case 13
. x x
x . x
x x x
All different patterns: 511^2
Permitted VPTs:
1. Transposing - 2 ways.
2. Swapping band1/band2 and stack1/stack2 - 2 ways.
3. Permutting rows in band1 - 6 ways.
4. Permutting rows in band2 - 6 ways.
5. Permutting columns in stack1 - 6 ways.
6. Permutting columns in stack2 - 6 ways.
Case 14
. x x
x x x
x x x
All different patterns: 511
Permitted VPTs:
1. Transposing - 2 ways.
2. Permutting rows in band1 - 6 ways.
3. Permutting columns in stack1 - 6 ways.
Case 15 (trivial)
x x x
x x x
x x x
All different patterns: 1, ED patterns: 1
To get ED anticorner patterns number one should compute numbers of ED patterns for each case and then sum them.
Serg
[Edited. I put disclamer "don't use this method" because described method is raw and wasn't proved in any way.]
Last edited by Serg on Wed Jun 12, 2024 9:23 am, edited 1 time in total.
- Serg
- 2018 Supporter
- Posts: 889
- Joined: 01 June 2010
- Location: Russia
