Symmetrical Givens

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

Re: Symetrical Givens

Postby 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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symetrical Givens

Postby Serg » Sat May 09, 2015 11:41 am

< withdrawn >
Last edited by Serg on Tue May 12, 2015 7:47 am, edited 3 times in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symetrical Givens

Postby 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 ?
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Symetrical Givens

Postby 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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symetrical Givens

Postby 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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symetrical Givens

Postby 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.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Symetrical Givens

Postby 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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symetrical Givens

Postby 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.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: Symetrical Givens

Postby 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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Symetrical Givens

Postby 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.
champagne
2017 Supporter
 
Posts: 5683
Joined: 02 August 2007
Location: France Brittany

Re: Symetrical Givens

Postby 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
.851......72.....3....7258...1..5.48..4..13....374.2...6..1..3..1..8.6.5.3.2.6.7.
........7.76..9..85..47...3...548...369...............1.3.9.4...5.8.16........1..
.369...8...5..3..2.4.7...36......249.........587.......5.1...2...9..8.61.61..4..7
75..31.....4.75...31.9.....1...293..24..5.7....37...2..3..98.1.48...7.5...15..8..
.............2.3.6...1.7.5.2.64.3..55.12..7.4.9...16..4..7....3.236.95...57..29.1
.36...25..417.5....5..3...4...5947.1...26.539...........93..4...74.19....23....96
16...4.92..4.2...69.2..643..1..47.252.5.683...........5.9.8.7.3.81.7..597....5.8.
5....9.2..2.58.6...9.1..5.4.3.8..4..8....1.324...93.6...1...246..6918............
8.3..1.45.1.82..96.......1.........7.867...247...58.39..92.5...36..4.............
.74...1..8......96..........386.12...6...2.4.2..4.8.31.831.95..5..8.7.13..95....7

Leren
Leren
 
Posts: 2902
Joined: 03 June 2012

Re: Symetrical Givens

Postby 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?
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Symetrical Givens

Postby 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
champagne
2017 Supporter
 
Posts: 5683
Joined: 02 August 2007
Location: France Brittany

Re: Symetrical Givens

Postby 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
Leren
 
Posts: 2902
Joined: 03 June 2012

Re: Symetrical Givens

Postby 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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

PreviousNext

Return to General