Automorphic patterns

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

Automorphic patterns

Postby coloin » Sun Feb 07, 2021 12:22 am

Patterns and Automorphic patterns

We have long investigated puzzles and their solution grids, and there are a small proportion of solution grids with > 1 automorphisms.

A stab at looking at the number of minimal puzzles per pattern was made here .

But really the numbers are too big and it is only at the edges C<21 , C>28 we can get close to an estimate by generating till puzzles dwindle with a neighbourhood search although the remote puzzles tend not to be found .....

Each puzzle can be morphed by exchanging the digits [9!] or swapping the rows colums boxes [2 x 6^8]

Each pattern can also be morphed up to 2 x 6^8 ways

The number of essentially different patterns has been worked out here

However .... its probably true that symmetry - eg diagonal symmetry must reduce the number of puzzles per pattern by half

Here are a sample pattern of each of the 15 27C puzzles with 3 diagonal/not in line clues -all Essentially Different patterns. [ED]

The #1 pattern had a surprizingly reduced number of puzzles in a run of the pattern [2 x 6^8 ways] over a large sample [100,000] of random grids

Code: Select all
                                                                                          Highest rated puzzle in patterns game     Estimate of number of minimal puzzles with this pattern   [x50000]

# 1   ..1..2..3.2..1..4.5..6..1....2..4..1.5..6..7.7..2..3....7..5..8.8..7..9.9..3..2.. #   C27/S4.da/M1.16.3     Patterns Game  16  ED = 10.6/10.6/9.8        2411
# 2   2...4...6..4..2.3..7.8..1....24...1.1...3...2.3...54....5..9.7..1.6..2..6...7...9 #   C27.M/S4.da/M1.31.2   Patterns Game 150  ED = 10.7/10.7/8.9      109551
# 3   ..2..3.1..3..1.2..5..6....4..5..7.2..9..4.8..6..9....7.8..9..5.2..5..4....3..8..9 #   C27/S2.d/M1.33.1                                                  98063
# 4   ..1.2.3...2...1..43..5...6...42...8.9...3...2.3...67...4...3..75..8...4...2.6.1.. #   C27.M/S2.p/M1.13.4                                               610993
# 5   1....2..3.9..4..1...73..5....21....9.6..2..5.9....56....3..41...7..8..2.2..6....8 #   C27.M/S4.da/M1.11.6                                               86740
# 6   2...3.1....14...2..5...6..3.6.2..4..3...5..7...7..3..65..8..7...9..1..4...6..2..9 #   C27/S2.d                                                         701514
# 7   .2..7...84..6..9....5..4.7..1.2..3..2...1...4..3..5.6..9.5..6....1..7..37...3..5. #   C27.M/S4.da/M1.16.1                                              641463
# 8   1..3..2...2..4..1...3..6..52...8..7..7.5..3....9..1..67...9.5...4.1....8..8..2.6. #   C27/S2.d              Patterns Game 410  ?                      1393902
# 9   ..2.1.3...1...2.4.5..3....2..5..7.8.6...3...4.4.6..9..7....4..6.3.2...5...4.9.7.. #   C27.M/S4.da                                                      695457
#10   ..1..2..3.2..1..4.3..5..6....51..2...4..7...12....8.3...96...7..6..4.3..8....7..4 #   C27 [asymmetric]  [no symetric pattern]                         1468539
#11   ..1..3..2.2..4..3.4..6..5....23...1..4...57..5...9...8..6.8..7..9.1..6..7....2..1 #   C27/S2.d                                                         257856
#12   2..1....3..1..2.4..5..3.6..5..7...9...6.8.2...8...4..1..7.6..8..6.4..1..3....7..5 #   C27/S4.da                                                        761411
#13   2...3.1....14...2..5...6..3.6.2..4..3....4.7...7.8...65..8..7...9..1..4...6..2..9 #   C27/S2.d                                                         389077
#14   6....2.7...8.1...5.9.5..3....2..1..3.1..2..4.5..3..2....4..8.9.1...9.8...3.4....7 #   C27.M/S4.da                                                      765426
#15   ..1.2...3.2...34..5..1...6...4..1.7.2...9...6.6.4..8...9...2..8..69...1.3...5.7.. #   C27.M/S4.da                                                      254596


The #1 pattern has the most reductions it would appear, they all have diagonal clues in the boxes and all have 27 clues

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


By my reckoning this pattern has ? 432 automorphs per pattern and there are 7776 different looking formations !! [432 x 7776 = 2 x 6^8]

[ 9 boxes,6 ways in a box, 2 x 2 ways for each band and chute, and one x 2 reflection] = 9x6x8 = 432

And this goes to explain why there were so many fewer puzzles compared with the other 27C puzzles

Apart from trivial 1, 81 and 9-template patterns ! this pattern may well be the pattern with the most automorphs

Maybe if we can confirm the automorphisms of these 15 ED [and there are only 15 ED ] patterns we can confirm the association
,
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon

Re: Automorphic patterns

Postby Serg » Wed Feb 10, 2021 2:36 pm

Hi, coloin!
I am not quite sure - is my understanding of your post true - but pattern automorphisms are really useful in exhaustive search tasks. When fully symmetric patterns were investigated, the knowledge of pattern's symmetries allowed to reduce number of puzzles to check from very huge to simply huge.

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

Re: Automorphic patterns

Postby coloin » Wed Feb 10, 2021 8:46 pm

Yes those fully symmetrical patterns have obvious automorphisms
and for example this 20C is fully symetrical - it can be reflected about the vertical horizontal and diagonal axis

Code: Select all
+---+---+---+
|...|1.2|...|
|..3|...|4..|
|.5.|...|.1.|
+---+---+---+
|9..|3.4|..6|
|...|...|...|
|4..|9.7|..2|
+---+---+---+
|.2.|...|.3.|
|..5|...|1..|
|...|2.8|...|
+---+---+---+
and same puzzle row swapped to change box 1
+---+---+---+
|...|1.2|...|
|..5|...|1..|
|.3.|...|.4.|
+---+---+---+
|9..|3.4|..6|
|...|...|...|
|4..|9.7|..2|
+---+---+---+
|.5.|...|.1.|
|..2|...|3..|
|...|2.8|...|
+---+---+---+

Back of a envelope calculation on the number of similar looking pattern isomorphs
So for every corner box there are 2 isomorphs and all can be reflected ...
so thats perhaps 4 x 2 x 2 = 16 isomorphs with this similar pattern

Its probably not an incorrect assuption that these patterns wont have as many puzzles as other similar 20 C patterns, and an exhaustive search for 20 clue puzzles was easier to accomplish.

and in the last page of the following thread [this is in relation to fully symmetrical invalid patterns] ... here

JPF wrote: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

Code: Select all
.........
....1....
...1.1...
..1...1..
.1.....1.
..1...1..
...1.1...
....1....
.........  32

1...1...1
.11...11.
.11...11.
....1....
1..1.1..1
....1....
.11...11.
.11...11.
1...1...1 64

111...111
111...111
111...111
....1....
...1.1...
....1....
111...111
111...111
111...111 192     


so maybe i have missed a x2
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon

Re: Automorphic patterns

Postby Serg » Wed Feb 10, 2021 10:28 pm

Hi, coloin!
Yes, JPF's examples (patterns) have 32/64/192 FS-automorphisms (as JPF wrote), but they have 32/512/41472 ordinary automorphisms (when all 3359232 VPTs are permitted).
coloin wrote:
Code: Select all
.........
....1....
...1.1...
..1...1..
.1.....1.
..1...1..
...1.1...
....1....
.........  32

1...1...1
.11...11.
.11...11.
....1....
1..1.1..1
....1....
.11...11.
.11...11.
1...1...1 64

111...111
111...111
111...111
....1....
...1.1...
....1....
111...111
111...111
111...111 192     


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

Re: Automorphic patterns

Postby coloin » Wed Feb 10, 2021 10:48 pm

Well i was wondering how there was so few .... I think these " ordinary automorphisms" are what i have in mind !!
But I would imagine that the more automorphisms a pattern has there may well be less chance of a valid puzzle - in the distinction between patterns which have valid puzzles and those that do not ...
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon


Return to General