The New Sudoku Players' Forum

[tarek]

Guys these puzzles are beautiful, well done. These Pi rotational symmetry puzzles are very pleading to the eye as well.

[eleven]

@blue: Yes, it's a known problem, that sometimes the ER differs by 0.1 for morphs.

The problem i had were missing constraints for cells, which are shared by both 2 symmetries. Thus the sticks symmetry could be "overwritten" by the other. After adding the constraints, my test results are subsets of yours.

Regarding the Quarter-Turn symmetry the four 10.4 puzzles turned out to be only 2 non equivalent. After 5 hours they kept to be the hardest (out of 31263 minimals):

Code: Select all

....8.4....14.2...3..9...2..1....87.9.......1.32....9..8...1..7...8.69....6.2.... 10.4 10.4 9.2   
..9...51.86...7.3.5.......8.4..2.......1.9.......8..6.2.......5.7.3...42.95...1.. 10.4 10.4 7.1   
..5.4..6.78.....1...4..17.5..8.7....3..4.6..7....3.2..5.39..6...9.....23.4..6.5.. 10.3 10.3 10.3   


PS: while the sticks symmetry puzzles I looked at, were trivial after entering the sticks numbers, the first one here was nice to solve with symmetry and four chains with max. 3 links (plus smmetric results).

[eleven]

Then I came up with something to work the other end of the size scale as well, though, and it worked wonders. A lot of the grids needed under a million tests, and none of them needed over 2.4 million. The average was 1.2 million.

What I did, was find the (minimal) unavoidable sets with size <= 9, and for each one:

• figure out the smallest symmetrical shape that covers the UA set
• take its complement, giving the largest symmetrical shape that fails to hit the UA set.
• set the "skip me" flag for that shape and all of its (symmetric) [/u]subset[/u] shapes.

I needed some time to understand, very clever (and i probably would need 3 weeks for that) !

[Leren]

A quick run through blue's minimal puzzles reveals that the following solve with singles only.

Hidden Text: Show

.32..74..7....41..4....1.98......987.........321......21.9....6..96....3..63..87.
..29..4..9..6..3..4..3....8......987.........321......2....7..6..7..4..1..6..18.
..53..8.49..6..3..2.49....5789.....................1235....16.8..7..4..16.2..75..
..53..8.6.7.6...1.2.69....5987.....................3215....14.8.9...4.3.4.2..75..
..29..4..9....43..4..3....8......987.........321......2....7..6..76....1..6..18..
..29..4..9....43..4..3....8.8....9.7.........3.1....2.2....7..6..76....1..6..18..
..89..4..9....43..4..3....2.8....9.7.........3.1....2.8....7..6..76....1..6..12..
...3..4.89..6..3..4.29...........987.........321...........18.6..7..4..12.6..7...
..59..4..8.9..42.34..3....5.8....9.7.........3.1....2.5....7..67.86..1.2..6..15..

Should these be removed from the list as being effectively trivial ?

Leren

[Serg]

Hi, blue!

A topic for another day: The '560' number for quarter turn symmetry, is also the number of general minlex solution grids (i.e. of 5.4e9), that have at least one transformation to a form that shows quarter turn symmetry. The numbers that eleven has given, and possibly Serg too, depending on how he used 'gridchecker' , seem to be that kind of number. That isn't quite what I've been calculating, which is more like the number of "symmetrically minlex" solution grids, that actually do show the symmetry. The difference would come down to what kinds of transformations are allowed, in producing the "minlex" grids from initial grids showing the symmetry -- any transformation at all, or only those that preserve the corresponding shape symmetry. For arbitrary symmetry types, it isn't clear to me, that the two kinds of numbers should match. Maybe I'm missing something ?

Let's consider all possible solution grids (6 x 10^21). Some of them have "quarter turn symmetry" property, so they form subset of all possible solution grids. Let's consider now all possible VPTs (3359232). Some of them preserve quarter turn symmetry, i.e. any quarter turn symmetric grid transformed by these VPTs will remain quarter turn symmetric grid (but maybe another quarter turn symmetric grid). For example, half turn rotation forever preserves quarter turn symmetry. Other VPTs may preserve symmetry for some quarter turn symmetric grid, but destroy symmetry for the rest symmetric grid, and can transform some non-symmetric grids to symmetric grid. My point is that it's no matter what kind of VPTs are considered. If two different quarter turn symmetric grids have the same minlex form, such grids can be transformed to each other by some VPT, so they are isomorphic. Hence it's no sense to consider both grids because they are similar. So, we can consider, say, the one having less "minlex quarter turn symmetric form" and discarding other (isomorphic) grid.

Sorry for saying trivial things. Why we usually avoid considering isomorphic solution grids? Because they are equivalent. So, if we know properties of the one of them, we know properties of others. For example, let a grid contains two 17-clue puzzles exactly. Then all its isomorphs will contain two 17-clue puzzles each, and each puzzle of isomorphs can be produced from considered puzzle by the transformation producing given isomorph.

I use the following method for symmetric grids processing.

1. Produce (by specially written program) list L1 of possible quarter turn symmetric grids in "minlex quarter turn symmetric form" (having 1,2,...9 in central box B5 and one digit "5" in the rest of the boxes). At this stage isomorphs are not filtered out.

2. Produce (by gridchecker) list L2 of "true" minlex forms for given symmetric grids list L1.

3. Start with empty "unique true minlex forms" list L3 and empty "ED quarter turn symmetric grids" list L4.

4. For each grid in L1 list check - is true minlex form of the grid (corresponding position in L2 list) in "unique true minlex forms" list L3? If "no" - put the grid in "minlex quarter turn symmetric form" to output list L4 and put true minlex form of the grid to L3 list. If "yes" - do nothing.

5. At the end we'll have output "ED quarter turn symmetric grids" list L4 in "minlex quarter turn symmetric form".

Serg

[blue]

Hi Serg,

Thanks for the detailed explanation. It looks like process you described (using lists L1,L2,L3,L4), is set up deliberately, in a way where you can be sure that no more than one final grid will be output, for each "true minlex" grid that can be made to show the quarter turn symmetry. For quarter turn symmetry, it turned out that that was "OK".

---

I've found an example of a different symmetry, where that sort of process, doesn't quite work -- or doesn't work, if the goal is to use the output grids as solution grids, to find all (minimal, say) puzzles with the symmetry in the givens as well. It's ordinary diagonal symmetry.

There are 23391 canonical grids, that can be made to show diagonal symmetry, but it turns out that you would need need 23511 solution grids, to produce a complete list of (ED) diagonally symmetric puzzles. The difference of 120, is exactly due to the (120 of 152) grids that can be made to show double diagonal symmetry, but that in the symmetric form, don't have an automorphism that exchanges the diagonals. (The 152-120 = 32 grids that do have such automorhisms, were mentioned in an earlier post).

For a (DD) solution grid like that (i.e. with no such automorphism), there are two sets of puzzles that can be produced -- the set of (valid) puzzles with diagonal shape symmetry, and the set with anti-diagonal shape symmetry. The two sets overlap in the set of puzzles with double diagonal shape symmetry. If you removed the DD puzzles from each list, you would find that no puzzle in one list, is isomorphic to a puzzle in the other list. If any were isomorphic, it would mean that the solution grid has an automorphism that exchanges the diagonals, and the assumption was that no such automorphism exists.

[blue]

Should these be removed from the list as being effectively trivial ?

Marked, maybe, but not removed ... since it the list of all minimal puzzles (factoring out isomorphs)

[Serg]

Hi, blue!

There are 23391 canonical grids, that can be made to show diagonal symmetry, but it turns out that you would need need 23511 solution grids, to produce a complete list of (ED) diagonally symmetric puzzles. The difference of 120, is exactly due to the (120 of 152) grids that can be made to show double diagonal symmetry, but that in the symmetric form, don't have an automorphism that exchanges the diagonals. (The 152-120 = 32 grids that do have such automorhisms, were mentioned in an earlier post).

For a (DD) solution grid like that (i.e. with no such automorphism), there are two sets of puzzles that can be produced -- the set of (valid) puzzles with diagonal shape symmetry, and the set with anti-diagonal[i] shape symmetry. The two sets overlap in the set of puzzles with [i]double diagonal shape symmetry. If you removed the DD puzzles from each list, you would find that no puzzle in one list, is isomorphic to a puzzle in the other list. If any were isomorphic, it would mean that the solution grid has an automorphism that exchanges the diagonals, and the assumption was that no such automorphism exists.

Would you post an example?

Serg

[blue]

Would you post an example?

Hi Serg,

Sure ...

Here's a grid with double diagonal symmetry, and no other automorphisms.

Code: Select all

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

This is a puzzle with that grid as its solution, that has diagonal anti-symmetry but not diagonal symmetry.

Code: Select all

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


Below, are two puzzles with the same solution, and diagonal, but no anti-diagonal symmetry.
In the large list of diagonally symmetric puzzles with that solution grid, you'll agree (I hope) that they are the only ones with a chance of being isomorphic to the first puzzle. (The missing case, with empty cells in boxes 1 and 9, has double diagonal symmetry too, and so no chance of being isomorphic to the first puzzle).

Code: Select all

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

Code: Select all

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

It turns out that they are isomorphic to each other, because of the pi-rotational symmetry of the solution grid, that comes along with double diagonal symmetry ... but neither one is isomorphic to the first puzzle.

The vertical reflection of the first puzzle, then, is an example of a puzzle with diagonal symmetry, that would not be generated (in any equivalent form), if only the original solution grid, appeared in the list of "ED" diagonally symmetric solution grids. You would need two different versions of the grid to be in the list, in order to get both (ED) puzzles generated.

If you like, you can try the same thing with the solution grid below, and discover see that all 3 puzzles are isomorphic.
It's one of the DD solution grids, that has 8 automorphisms all together, including one that does swap the diagonals.

Code: Select all

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

Best Regards,
Blue.

[eleven]

I have not verified that, but I think, the diagonal and the sticks symmetries are the only ones, which can be twice in a grid, without automatically having an automorphism (by Quarter-Turn symmetry), which morphs one to the other.
So if someone wants to find all minimal diagonal or sticks symmetric puzzles from grids with that symmetry, this has to be taken into account.
But who should start such a big job ?

[champagne]

So if someone wants to find all minimal diagonal or sticks symmetric puzzles from grids with that symmetry, this has to be taken into account.
But who should start such a big job ?

With that wording, I have doubts that I really catch your point.

For me, blue did the job for a double diagonal symmetry. I am still working at checking the results using another process.

What exactly have you in mind ?

2 times a stick symmetry in the same puzzle,
a mix of diagonal and stick symmetry?

It could be that some examples of such cases have been given above, but this thread is so active that i can have missed them.

[eleven]

So if someone wants to find all minimal diagonal or sticks symmetric puzzles from grids with that symmetry, this has to be taken into account.
But who should start such a big job ?

With that wording, I have doubts that I really catch your point.

For me, blue did the job for a double diagonal symmetry.

champagne,

i am sorry that i did not formulate that clearer. This was a response to the discussion of blue and Serg. I meant the job to find all (minimal) puzzles with single diagonal/sticks symmetry, and there are a lot more.

[champagne]

i am sorry that i did not formulate that clearer. This was a response to the discussion of blue and Serg. I meant the job to find all (minimal) puzzles with single diagonal/sticks symmetry, and there are a lot more.

I fully agree with you

First of all, many more solutions grids,many more patterns, but also, many more possibilities in one pattern to combine the clues.

my experience of the pattern game is that each diagonal pattern (no stick symmetry in the pattern game) produces hundreds of puzzles (if not thousands) and the process, with my poor code lasts about 15 minutes. As noticed mike earlier, in the pattern game it's worth to do it at the start for 2 reasons,

- some good puzzles for the game appear
- the process supply an interesting set of seed for further processing.

[Serg]

Hi, blue!
I caught your idea.
Solution grid

Code: Select all

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

and its "reflection" solution grid, produced from original grid by reflecting it about vertical symmetry axis, both are presented in the "ED diagonal symmetric solution grids" list by the same representative (namely - by original grid). So, if we would check grids from this list for having diagonally symmetric puzles by appling patterns that are symmetric about main diagonal only, we would miss puzzle

Code: Select all

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


Actually it should be presented in diagonally symmetric view

Code: Select all

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


I'd call this problem as "broken automorphisms problem". I faced with it many times while doing exhaustive search projects. For example, it arises when we try to combine two possible band contents in the same grid, starting with e-d bands list. To my mind, "broken automorphisms problem" was the most complicated problem that I have encountered in exhaustive search projects. Some time ago I managed to find more or less systematic approach to its processing. But I need some time to recover (in my mind) that approach.

Nevertheless, when we are discussing diagonal symmetric solution grids themselves, we should state that 23391 (this number is copied from your post, I am not able to confirm it yet), not 23511, from 5472730538 essentially different sudoku solution grids can be morphed to diagonally symmetric view.

Serg

[eleven]

I faced with it many times while doing exhaustive search projects. For example, it arises when we try to combine two possible band contents in the same grid, starting with e-d bands list.

Would you post an example?