The New Sudoku Players' Forum

by **Serg** » Sat May 09, 2015 8:13 am

Hi, eleven!

eleven wrote:
Serg wrote: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?

Sure ...

But I need some time to prepare an example.

Serg

by **Serg** » Sat May 09, 2015 11:41 am

< withdrawn >

by **eleven** » Sat May 09, 2015 10:07 pm

Serg,

what kind of patterns (can be almost everything) do you have in mind here, i suppose not only symmetrical givens ?

by **Serg** » Sun May 10, 2015 12:02 am

Hi, eleven!

eleven wrote:Serg,
what kind of patterns (can be almost everything) do you have in mind here, i suppose not only symmetrical givens ?

In "formal description" part of my post I meant arbitrary pattern, but in "informal part" I meant symmetric (about main diagonal) patterns, because that was "example".

I'm not sure - did I correctly understand your question?

Serg

by **Serg** » Sun May 10, 2015 12:46 am

Hi, eleven!

eleven wrote:
Serg wrote: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?

Here is an example of "broken automorhisms problem" concerning exhaustive search projects.

Let's find all valid puzzles for the pattern

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| +-----+-----+-----+

Following method of blue (based on Red Ed ideas), I switched from searching possible clue value combinations to searching possible free cells value combinations. So, I searched for possible completions for this pattern.

To speed up search is essential to find all valid completions (i.e. not containing unhitted UA sets) for the pattern

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| +-----+-----+-----+

first, and then combine bands (B1, B2, B3 boxes) and stacks (B1, B4, B7 boxes).

It turns out this one-band-free patterns has 274 valid completions only. It is because of rather large number of automorphisms for those completions - 144 automorphisms (I counted automorphisms involving free cells only, so "dummy" automorphisms like swapping bands B456 and B789 was not calculated).

Next step - assembling original pattern's completions (free band + free stack) using 274 valid completions for a band (stack). We can use those 274 valid completions for B123 band, but must consider more variants for stack B147 completions, because filled B123 band "brokes" some automorphisms of the stack - swapping columns c1/c3 and swapping rows r1/r3 are not allowed for B147 stack now, because it could destroy minimal form of B123 band. So, we need to produced additional isomorphs for each stack's completion taken from 274 valid completions list (3 additional isomorphs for each completion).

Serg

by **eleven** » Sun May 10, 2015 3:26 pm

Thanks for the example, Serg.

I see, that we have a similar situation here in the sense, that the list of solution grids, where the pattern is possible, has to be extended because of an automorphism.

But here the additional grids are essential different to the others, while in the "symmetrical givens" case a (double symmetrical) grid has to be searched twice (for both symmetries) - if there is not an automorphism there from one to the other symmetry.
Also the reason, why the additional grids have to be considered, in this case is a pattern automorphism, in the other an additional grid automorphism.

by **Serg** » Sun May 10, 2015 6:31 pm

Hi, eleven!

eleven wrote:But here the additional grids are essential different to the others, while in the "symmetrical givens" case a (double symmetrical) grid has to be searched twice (for both symmetries) - if there is not an automorphism there from one to the other symmetry.

In blue's example we should process additional solution grid being isomorphic to original solution grid. Additional grid isn't another e-d solution grid, but isomorph of original solution grid. Such approach (adding isomorphs to input grids' list) is convenient way of accounting extra automorphisms (like reflection about anti-diagonal).

Please note, that if we would consider pattern, having diagonal and anti-diagonal symmetries, we would not need to process additional isomorph (anti-diagonal symmetry would not be broken).

Serg

by **eleven** » Sun May 10, 2015 8:12 pm

Hm, are you repeating, what i said ?

What you did not repeat is
- that you do not need to process an isomorph solution grid , if it has Quarter Turn symmetry
- that your sample has not much more in common with blues' than that both are about handling automorphisms correctly.

by **Serg** » Sun May 10, 2015 8:59 pm

Hi, eleven!

eleven wrote:... you do not need to process an isomorph solution grid , if it has Quarter Turn symmetry.

Please, clarify your point.

Serg

by **champagne** » Mon May 11, 2015 5:15 pm

I wrote earlier that I'll try to cross check blue's results for the double diagonal symmetry

I have now a code not too far from what I intend to do, although I still have to improve the use of the brute force;

On top of the 20 puzzles with 20 clues produced by blue, I got that list

98.......6......5.....123.....9..6....1...9....4..1.....789.....5......4.......21 ED=7.1/1.2/1.2
1...4.......2...7....3..5...479.....2.......8.....136...5..7....3...8.......6...9 ED=3.6/3.6/2.6
98......36..........5.12......9..6....1...9....4..1......89.5..........47......21 ED=1.5/1.2/1.2
5..1......9..........24.3..1.4..3.....2...8.....7..6.9..7.68..........1......9..5 ED=2.0/1.2/1.2
98......36......5.....12......9..6....1...9....4..1......89.....5......47......21 ED=1.5/1.2/1.2
98.......6......5.....12......9.36....1...9....47.1......89.....5......4.......21 ED=1.7/1.2/1.2
98.......6......3.....12......9.36....1...9....47.1......89.....7......4.......21 ED=1.7/1.2/1.2
96...1...81.....3......27........6.9.........1.4........38......7.....92...9...41 ED=1.2/1.2/1.2

The only thing I did not do at that level is to check for minimal, but I have some difficulty to imagine that a symmetry of given of 20 clues can "not be minimal".

Interesting point, the overall run time at that level was below 2 minutes.

by **Leren** » Tue May 12, 2015 1:48 am

Here's a sample of 10 puzzles that exhibit row and column stick symmetry. My understanding is that they are not minimal.

Hidden Text: Show

Leren

by **dobrichev** » Tue May 12, 2015 4:58 am

Hi Leren,
To my understanding your puzzles are minimal, i.e. have no redundant clues.

I took the seventh puzzle and ... hit bugs in my software tools.

Code: Select all: 16.4..9.2..4..2..69.26..34..1.7.42.5.........2.58.6.3..81..75.97..5..8..5.9..8.73 #Leren's #7 with (wrong 7, likely 4) automorphisms 168473952374952186952681347816734295437295618295816734681347529743529861529168473 #its solution with (wrong 14, likely 4) automorphisms 1 6 . 4 . . 9 . 2 . . 4 . . 2 . . 6 9 . 2 6 . . 3 4 . . 1 . 7 . 4 2 . 5 . . . . . . . . . 2 . 5 8 . 6 . 3 . . 8 1 . . 7 5 . 9 7 . . 5 . . 8 . . 5 . 9 . . 8 . 7 3 #Morph with 4x90deg rotational symmetry (+ other wrong symmetries = 7, but likely 4) automorphisms 168473952374952186952681347816734295437295618295816734681347529743529861529168473 #morph's solution with (wrong 12, likely 4) automorphisms 123456789456789123789123456231567894597834261864291537312678945678945312945312678 #minlex morph of the solution with 4? automorphisms 1..4..7....6.891.3..91.3.56.........5.78.4.6.8.4.9.5.7..2..8..56..94.3.29..3.267. #puzzle in minlex solution with 4? automorphisms

Assuming there is single error in the puzzle/solution automorphisms counting, and taking into account that puzzle automorphisms must be <= solution automorphisms, then both the puzzle and its solution should have 4x90 deg rotational symmetry only.
Can somebody confirm?

by **champagne** » Tue May 12, 2015 5:46 am

dobrichev wrote:Assuming there is single error in the puzzle/solution automorphisms counting, and taking into account that puzzle automorphisms must be <= solution automorphisms, then both the puzzle and its solution should have 4x90 deg rotational symmetry only.
Can somebody confirm?

my tool can produce a central symmetry in that morph

Code: Select all: 16...49.2 ..42....6 9.2..634. .1.4.72.5 ......... 2.56.8.3. .817..5.9 7....58.. 5.98...73

I can't see any stick in the original puzzle.

I have no evidence so far of a R90 symmetry

by **Leren** » Tue May 12, 2015 7:14 am

Champagne wrote ; I can't see any stick in the original puzzle.

This is a PM for the 7th puzzle in my list showing the row and column stick elimination cells marked with * and #.

Code: Select all: *--------------------------------------------------------------* | 1 6 378 | 3578 35 4 | 58 9 2 | | 38 357 4 | *59 *2 *9 | 158 17 6 | | 9 57 2 | 1578 15 6 | 4 3 178 | |--------------------+--------------------+--------------------| | 368 #1 368 | #39 4 7 |#9 2 5 | | 2 #9 5 | #19 6 8 |#3 147 147 | | 3468 #39 3678 |#*9 *59 *29 |#19 1467 1478 | |--------------------+--------------------+--------------------| | 5 24 9 | 1246 8 12 | 7 146 3 | | 346 8 1 | 2346 7 23 | 26 5 9 | | 7 234 36 | *29 *9 *5 | 126 8 14 | *--------------------------------------------------------------*

Leren

by **Serg** » Tue May 12, 2015 7:45 am

Hi, blue!

blue wrote: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 ?

I found principal error in my method of accounting "broken automorphisms" in searching for main diagonal symmetric puzzles. It can be applied to grid fragments combining tasks, but cannot be applied to correct production of other instances of main diagonal symmetric solution grid. So, I withdrew my method description.

This problem is not so simple.

Serg

The New Sudoku Players' Forum

Symmetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens

Re: Symetrical Givens