The New Sudoku Players' Forum

by **blue** » Sun May 03, 2015 9:54 pm

eleven wrote:I did not understand everything, e.g. how did you verify, that this cannot be a superset of a symmetrical solution?
Code: Select all
1 . . . . 5 . . 3 . 5 . . . . . 7 . . . 9 . . . 5 . . . . . 1 2 3 . . 5 . . . 4 5 6 . . . 5 . . 7 8 9 . . . . . 5 . . . 1 . . . 3 . . . . . 5 . 7 . . 5 . . . . 9

This one can be transformed in a way that looks like it just moves the 5 from r1c6 to r1c4 (to match the #3 seed grid from above) ...like this:

eleven wrote:Of course now i ask myself, if also the other 2 symmetries with 4 automorphisms, 90 degree rotational and 180 degree rotational combined with sticks symmetry could be searched exhaustively (but i would not expect high ratings there).

I realized a few hours ago, that the problem for 90 degree rotational puzzles would be comparable in size to the double diagonal case.
You can use a process similar to what I described, using a 21-bit shape mask (2M shapes), and one seed grid.

Code: Select all: x x x | x x x | x x . . x x | x x x | x . . . . x | x x x | . . . ------+-------+------ . . . | x x . | . . . . . . | . x . | . . . . . . | . . . | . . . ------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .

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

There would be more solution grids, but fewer shapes to test for each one, than with DD symmetry.

by **blue** » Sun May 03, 2015 10:05 pm

champagne wrote:Unless I miss something, you can apply vertical symmetry and exchange of rows and columns to reduce the count and I don't see that in your text.
more or less, the vertical symmetry alone should halve the count.

Good point.
Yes, it would have saved half the time ... but only for the 32 grids that have 8 (rather than 4) "dd-shape-preserving" automorphisms.
Overall, it would have saved around 10% of the time, and removed the need to check for isomorphs in the list of minimal puzzles.

by **blue** » Sun May 03, 2015 10:24 pm

Serg wrote:Do all 50781 puzzles are minimal in the sense that no clues can be deleted provided that remaining puzzle will have unique solution AND will still have diagonal and antidiagonal symmetries among its clue values? (eleven call such kind of minimality as "minimal to symmetric clues".)

No, they were just the "truly minimal" puzzles.
"Symmetrically minimal", is another term that I've seen used, to describe the other kind of puzzle.
There would be ~1.8 million of those, I think ... (50781/59034)*2134808, using numbers from my earlier post.

by **Serg** » Mon May 04, 2015 9:00 am

Hi, blue!

blue wrote:Here are the puzzles (I hope).
...
Anyone else is welcome to download the files, combine them and share them via some other means.

Thanks for puzzles!
I uploaded them in the file "dd-raw.zip" (all 3 parts are concatenated) on my page: http://sites.google.com/site/sergsudoku/dd-raw.zip.

Serg

by **eleven** » Mon May 04, 2015 4:17 pm

blue wrote:This one can be transformed in a way that looks like it just moves the 5 from r1c6 to r1c4 (to match the #3 seed grid from above) ...like this: ...

Thanks, i was too lazy to try to find the transformation myself, instead i trusted gsf's outcome, which were different canonicalizations. But (i should have known) it cannot be used for multi-solution puzzles to determine, if they are essential different (ed).

I realized a few hours ago, that the problem for 90 degree rotational puzzles would be comparable in size to the double diagonal case.
...
There would be more solution grids, but fewer shapes to test for each one, than with DD symmetry.

Much more: Red Ed had calculated the number of grids for 90° rotational symmetry (quarter turn) as 13.056.

The sticks symmetry is the most common one (and least known) under the solution grids.
You exchange bands 1 and 3 as well as columns 13,46 and 79.
Thus in bands 1,3 the mini-columns 1/2/3 of each box move to 3/2/1 in the other band, and in the middle band mini-columns 1/4/7 switch with 3/6/9, while mini-columns 258 are fixed (containg the same 3 numbers).
The second common symmetry is 90 degree rotational (pi rotational, half-turn).

I made a quick test for the combination of the two, and got 10000 ed grids for the first 100K and 3000 more for the second 100K solution grids. So i expect more than [edit:]20000 grids with this symmetry.
The percentage of the minimal puzzles out of the "symmetric minimal" ones is very small, i got only 81 from almost 200K (55 with rating > 7, highest rating 9.1). So in minimal puzzle sets they must be very rare.

Code: Select all: +-------+-------+-------+ | . . 2 | 9 . 8 | 4 . . | | 9 . . | 4 . . | 1 . . | | 4 . . | 1 . 3 | . . 7 | +-------+-------+-------+ | 8 . 7 | . . . | . 9 . | | . . . | . . . | . . . | | . 1 . | . . . | 3 . 2 | +-------+-------+-------+ | 3 . . | 7 . 9 | . . 6 | | . . 9 | . . 6 | . . 1 | | . . 6 | 2 . 1 | 8 . . | +-------+-------+-------+ ER 9.1, stick cycles (1),(2,3),(4,6),(5),(7,8),(9)

An exhaustive search for puzzles with this Pi/Stick symmetry therefore is probably much more effort than for DDS.

by **champagne** » Mon May 04, 2015 5:25 pm

just one message to jasonlion. (I'll use pm if he does not have a look at it)

The symmetry topic takes now an important place here.

I think it would be good to move all that stuff in a dedicated thread to have a chance to find it easily later.

Split into it's own topic. JasonLion

To blue,

nothing to add "a priori" to your quick and efficient search for DD's symmetric puzzles.

I'll try to cross check the result using the basic symmetries to see what is the effect on the task.

The vertical symmetry is quite clear; I had some doubts about the rows permutations in band 1, but as it is a valid permutation in the final puzzle, it can be used with specific rules.

So, if I am right, any pattern not "maximal" using one of these perms can be discarded.

by **blue** » Mon May 04, 2015 9:22 pm

Serg wrote:Thanks for puzzles!
I uploaded them in the file "dd-raw.zip" (all 3 parts are concatenated) on my page: http://sites.google.com/site/sergsudoku/dd-raw.zip.

Super

I've edited my earlier post.

Thank you again,
Blue.

by **blue** » Tue May 05, 2015 9:53 am

champagne wrote:The vertical symmetry is quite clear; I had some doubts about the rows permutations in band 1, but as it is a valid permutation in the final puzzle, it can be used with specific rules.

So, if I am right, any pattern not "maximal" using one of these perms can be discarded.

I don't understand 100%, what you're planning.
What can be done, will depend on the particular solution grid.
For some of the grids, you can't discard any of the patterns. You're OK with that ?

by **champagne** » Tue May 05, 2015 10:29 am

blue wrote:
champagne wrote:The vertical symmetry is quite clear; I had some doubts about the rows permutations in band 1, but as it is a valid permutation in the final puzzle, it can be used with specific rules.

So, if I am right, any pattern not "maximal" using one of these perms can be discarded.

I don't understand 100%, what you're planning.
What can be done, will depend on the particular solution grid.
For some of the grids, you can't discard any of the patterns. You're OK with that ?

Hi blue,

Give me on or 2 more days to clarify some points and i'll come back to you, may be through pm first to avoid annoying discussions for others.

Basically I did not intended to use directly your solution grids, but to follow the following process

. solve directly the ED patterns of "final" size (n<24) (ED against the available symmetries)

. solve next levels using previous patterns giving no solution,
. finding ED pattern adding one clue to size n-2 or n-4 depending on the clue added
. solving directly those pattern.

This is another way to consider your "super setting" concept which I feel very important to reduce the count.

No idea so far about the feasibility of that approach, but if it works, the same concept could be applied to other symmetries.

by **Serg** » Tue May 05, 2015 1:32 pm

Hi, all!
I confirm blue's result about 152 essentially different solution grids, having both diagonal and antidiagonal symmetries. (I wrote a program performing exhaustive search.)

Serg

by **eleven** » Tue May 05, 2015 4:00 pm

eleven wrote:Much more: Red Ed had calculated the number of grids for 90° rotational symmetry (quarter turn) as 13.056.

Hm, i don't know what Red Ed's "Number of invariant grids" is, but it cannot be the number of non equivalent solution grids containing the symmetry.
I got 2 times the same 560 grids from 100K puzzles (and four 10.4 puzzles in 1 hour).
So different to the Pi/Sticks symmetry the 90°digit symmetry (which seems to have harder puzzles) should be calculable in reasonable time.

by **Serg** » Tue May 05, 2015 8:15 pm

Hi, eleven!

eleven wrote:I got 2 times the same 560 grids from 100K puzzles (and four 10.4 puzzles in 1 hour).
So different to the Pi/Sticks symmetry the 90°digit symmetry (which seems to have harder puzzles) should be calculable in reasonable time.

I've done exhaustive search for solutions grids having quarter turn symmetry. You are right. There exist 560 essentially different such solution grids. Program ran less than 1 second, plus gridchecker execution (sorting out isomorphs) - several seconds. I have used blue's method.

Serg

by **blue** » Wed May 06, 2015 10:03 am

Serg wrote:Hi, eleven!
eleven wrote:I got 2 times the same 560 grids from 100K puzzles (and four 10.4 puzzles in 1 hour).
So different to the Pi/Sticks symmetry the 90°digit symmetry (which seems to have harder puzzles) should be calculable in reasonable time.

I've done exhaustive search for solutions grids having quarter turn symmetry. You are right. There exist 560 essentially different such solution grids. Program ran less than 1 second, plus gridchecker execution (sorting out isomorphs) - several seconds. I have used blue's method.

I had 560 as well, but see the note at the bottom of this post.

For the Pi/Sticks symmetry (equivalent to "row sticks"+"column sticks") ... I got 2320 "ED" solution grids, using this as a seed grid:

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

I did the search for minimal puzzles having the same kind of shape symmetry, and got an amazingly small number of them: 62 (listed below).

There were 2^25 shapes for this one too ... the same as for double diagonal symmetry ... but my trick to reduce the number that needed to be tested, didn't work well at all. The smallest valid puzzles were too few, and too large, to be of much help. About 29,000,000 shapes needed to be tested, for each grid.

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) subset shapes.

The minmal puzzles are here:

Hidden Text: Show

None of them were especially hard -- 9.2, was the highest SE rating.
All of them had at least 24 givens, and only one of them used r5c5.

There was one with size 36:

Code: Select all: . 3 2 9 . . 4 . 5 9 . . . . 4 3 . . 4 . 5 3 . . . 9 8 6 . 4 1 . 3 . 8 . . . . . . . . . . . 2 . 7 . 9 6 . 4 2 1 . . . 7 5 . 6 . . 7 6 . . . . 1 5 . 6 . . 1 8 7 . ED=8.5/7.2/7.2

---

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 ?

by **eleven** » Wed May 06, 2015 12:39 pm

blue wrote:For the Pi/Sticks symmetry (equivalent to "row sticks"+"column sticks") ... I got 2320 "ED" solution grids, using this as a seed grid: ...

But this isn't the only possible (ed) seed grid, is it ?
E.g. what's wrong with this puzzle ?

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

[Edit: Ah, this puzzle is in your list. Have to look at the others.

by **blue** » Wed May 06, 2015 1:53 pm

eleven wrote:E.g. what's wrong with this puzzle ?
Code: Select all
+-------+-------+-------+ | 6 . 9 | 8 . . | . 3 7 | | . . . | . . 6 | . . . | | . 8 2 | 3 . . | 6 . 1 | +-------+-------+-------+ | 4 . 6 | . . . | . 9 . | | 8 . 7 | . . . | 3 . 2 | | . 1 . | . . . | 4 . 6 | +-------+-------+-------+ | 9 . 4 | . . 7 | 8 2 . | | . . . | 4 . . | . . . | | 3 7 . | . . 2 | 1 . 4 | +-------+-------+-------+ ER 9.3

[Edit: Ah, this puzzle is in your list. Have to look at the others.

It's interesting though.
The one in the list rates at 9.2 !

P.S. Sorry about the mix up with your name, in my last paragraph above ... fixed now.

The New Sudoku Players' Forum

Symmetrical Givens

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens