## The best symmetry

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

### The best symmetry

Let's consider a puzzle (or a pattern) :

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

This puzzle (Easter Monster) doesn't have any symmetry.
There is no symmetry s such that for every clue c, s(c) is a clue.

But what is the "best" symmetry ?

Let's consider this isomorphic :
Code: Select all
` *-----------* |..2|...|..1| |.5.|..4|.9.| |7..|...|6..| |---+---+---| |...|3.9|.5.| |...|.7.|...| |.4.|.58|...| |---+---+---| |6..|...|..7| |.8.|9..|.3.| |..1|...|2..| *-----------*`

If s is the anti-diagonal symmetry, then for every clue c (except r6c5) , s(c) is a clue of the puzzle.

Easter Monster has a symmetry modulo 1.

Finding by hand the best symmetry of a puzzle is an interesting but not easy exercice.

Here is tarek's Golden Nugget :
Code: Select all
` *-----------* |...|...|.39| |...|..1|..5| |..3|.5.|8..| |---+---+---| |..8|.9.|..6| |.7.|..2|...| |1..|4..|...| |---+---+---| |..9|.8.|.5.| |.2.|...|6..| |4..|7..|...| *-----------*`

Are you able to find its "best" symmetry ?

What is the maximum value of a best symmetry ?

JPF
JPF
2017 Supporter

Posts: 6090
Joined: 06 December 2005
Location: Paris, France

### Re: The best symmetry

JPF wrote:Here is tarek's Golden Nugget :
Code: Select all
` *-----------* |...|...|.39| |...|..1|..5| |..3|.5.|8..| |---+---+---| |..8|.9.|..6| |.7.|..2|...| |1..|4..|...| |---+---+---| |..9|.8.|.5.| |.2.|...|6..| |4..|7..|...| *-----------*`

Are you able to find its "best" symmetry ?

I could do no better than diagonal symmetry modulo 3 (r4c7, r5c4, r7c5).
Code: Select all
` 1 . . | . . . | . . 4 . 7 . | . . . | . 2 . . . 8 | 6 . . | 9 . .-------+-------+------- . . 3 | . . 8 | 5 . . . . . | 9 3 . | . . . . . . | 5 . . | . 1 .-------+-------+------- . . 9 | . 5 . | 8 . . . 2 . | . . 6 | . . . 4 . . | . . . | . . 7`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:I could do no better than diagonal symmetry modulo 3 (r4c7, r5c4, r7c5).
Code: Select all
` 1 . . | . . . | . . 4 . 7 . | . . . | . 2 . . . 8 | 6 . . | 9 . .-------+-------+------- . . 3 | . . 8 | 5 . . . . . | 9 3 . | . . . . . . | 5 . . | . 1 .-------+-------+------- . . 9 | . 5 . | 8 . . . 2 . | . . 6 | . . . 4 . . | . . . | . . 7`

I wrote:What is the maximum value of a best symmetry ?
My question was not clear.

Let's take an example :
Code: Select all
` 4 . . | . 2 . | . . 8 . . . | 8 . . | 4 3 . 7 5 . | . . . | . 2 .-------+-------+------- 5 . . | 7 . . | . 1 . . . 3 | . . . | . . 9 6 . . | 9 8 . | . . .-------+-------+------- 1 8 5 | . . . | 6 . 4 . . . | 6 . . | . . 2 . . . | . 7 . | . 9 3`

For this puzzle, the best symmetry is a 180-degree rotationnal or a diagonal symmetry modulo 9

Here are examples :
Code: Select all
` *-----------* |4..|..2|..8| |...|8..|34.| |75.|...|2..| |---+---+---| |5..|7..|1..| |6..|9.8|...| |..3|...|..9| |---+---+---| |185|...|.64| |...|..7|9.3| |...|6..|..2| *-----------*   180-degree rotationnal`

Code: Select all
` *-----------* |8..|.4.|..2| |.43|...|8..| |..2|57.|...| |---+---+---| |..1|.5.|7..| |9..|..3|...| |...|.6.|9.8| |---+---+---| |46.|815|...| |2..|...|6..| |3.9|...|..7| *-----------*   diagonal`

The initial puzzle has a symmetry modulo 9.

Could we find minimal puzzles with symmetry modulo n ; n>9 ?

JPF
JPF
2017 Supporter

Posts: 6090
Joined: 06 December 2005
Location: Paris, France

### Re: The best symmetry

JPF wrote:.... This puzzle (Easter Monster) doesn't have any symmetry.
There is no symmetry s such that for every clue c, s(c) is a clue. ....

Depends how you define "symmetry".

Obviously, at the very least, a symmetry is a one-to-one map of the 9x9 grid onto itself. Beyond that, though, the requirements seem a bit fuzzy. For example, if s is a symmetry, is it required that s(s(x))=x for all cells x?

So far, the identity map s(x)=x is a symmetry, but I assume that's too trivial to qualify. Besides the identity map, what else does not qualify?

Obviously, we cannot insist that s(x) be distinct from x for all x (at least not if we want s(s(x))=x, because then the cells would come in pairs, and there's an odd number of cells).

Of course, there are the various "common" symmetries, such as diagonal, rotational, horizontal, vertical, as well as those involving automaps of the digits 1-9. But does anybody have an exact definition?

Bill Smythe
Smythe Dakota

Posts: 564
Joined: 11 February 2006

Smythe Dakota wrote:Of course, there are the various "common" symmetries, such as diagonal, rotational, horizontal, vertical, as well as those involving automaps of the digits 1-9. But does anybody have an exact definition?

For what you call the common symmetries, see these topics from Gordon Royle :In my post, I was refering to those pattern-symmetries of order 2 (Type V, VI, VII in the Gordon's taxonomy).

JPF
JPF
2017 Supporter

Posts: 6090
Joined: 06 December 2005
Location: Paris, France

Other than brute force, i.e., comparing all 6^8 isomorphs against symmetric patterns, do you have an algorithm to determine best symmetries?
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:Other than brute force, i.e., comparing all 6^8 isomorphs against symmetric patterns, do you have an algorithm to determine best symmetries?
brute force ... to avoid bugs in my program

JPF
JPF
2017 Supporter

Posts: 6090
Joined: 06 December 2005
Location: Paris, France

I like this idea of best symmetry.........

How doeas the algorithm go.....

My initial idea is
Code: Select all
`1. C=original number of clues; n=0; S=1; N=812. remove  n clues from the puzzle3. go through all pozzible permutations (6^8)4. if symmetry encountered Record "s (symmetry 2-8) Modulo n"5. if s >=S && n<=N then S=s; N=n6. if all possible combinations of n clues have been removed && S>1 then  goto 107. return the removed clues8. n++9. if n<C then goto 210. best symmetry is "S Modulo N"`

tarek

tarek

Posts: 3761
Joined: 05 January 2006

tarek wrote:I like this idea of best symmetry.........
How doeas the algorithm go.....
Thanks.

My algorithm :
Code: Select all
`1. P = original puzzle ; N=812. For each Q = isomorphic of P  [2* x 6^8 values]3. For a symmetry s()    [ s = V, VI, VII ]4. n=05. For each clue c of Q6. if s(c) is not in Q then n=n+17. next c8. if n<N then Sm=s and Qm=Q and N=n9. next s10. next QBest symmetry = Sm (modulo N), with puzzle Qm `
* not sure if 2 is usefull or not (transposition)

JPF
JPF
2017 Supporter

Posts: 6090
Joined: 06 December 2005
Location: Paris, France

I've also posted a query on the hardest thread.....

If you had 1000 isomorphs of the same puzzle, the end product of prceesing all of these pzzles through the algorithm should be consistant.

Algorithm:
Code: Select all
`1. Po=Original Puzzle2. M(absolute)=Po number of clues, S(absolute)=2 Ip(absolute)=Po3. Ip(x)= Isomorph of Po (where x is a range 2*6^8)4. S = Symmetry order (1,2,4,8)5. M(x)=Minmum number of clues removed from Ip(x) to establish S6. Sp(x)=Ip(x) without M(x)7. if M (x)<M(absolute) then M(absolute)=M(x) S(absolute)=S Ip(absolute)=Ip(x) Sp(absolute)=Sp(x)8. if M(x)==M(absolute)  AND S> S(absolute)then M(absolute)=M(x) S(absolute)=S Ip(absolute)=Ip(x) Sp(absolute)=Sp(x)9. if M(x)==M(absolute)  AND S==S(absolute) then if boolean Sp(x)<boolean Sp(absolute) thenM(absolute)=M(x) S(absolute)=S Ip(absolute)=Ip(x) Sp(absolute)=Sp(x)Maximal symmetry = Ip(absolute) symmetryModulo = M(absolute)`

The above busy algorith would generate (I think) consistant results

tarek

tarek

Posts: 3761
Joined: 05 January 2006

[ transferred from The Hardest Sudoku thread ]
tarek wrote:
gsf wrote:I'm looking at my symmetrize routine to allow for errors
so that it will determine the closest symmetry via a distance measure
that would be great, I'm assuming that it should give consistant results for 100 isomorphs of the same puzzle as a test.

here's what it got for coloin's 4 grids
it produces the same pattern for isomorphic permutations
per ronk's suggestion this one ignores the center box in the symmetry distance
distances: 4 6 4 6
symmetries: pi diag pi diag
still working on the related data output
Code: Select all
`. . .  . . 1  . . 5. 3 .  . . .  . 7 .. . 2  . 8 .  6 . .. . .  6 . 8  9 . .. . 8  4 . .  . . .9 . .  . 2 .  . . .. . 6  . 4 .  2 . .. 7 .  . . .  . 1 .5 . .  . . .  . . 3. . .  . . .  . . 3. . 6  . . 9  2 . .. 7 .  . 2 .  . 1 .. . .  4 . .  . . .. . 9  . . 6  4 . .5 . .  9 . 8  . . .. 3 .  . . .  . 7 .. . 2  8 . .  6 . .1 . .  . . .  . . 5. . .  . . 1  . . 7. 3 .  . . .  . 5 .. . 8  . 2 .  6 . .. . .  4 . .  9 . .. . 4  6 . 2  . . .8 . .  . 9 .  . . .. . 6  . 4 .  2 . .. 7 .  . . .  . . 15 . .  . . .  . 3 .. . .  . . .  . . 7. . 2  . . 8  6 . .. 1 .  . 4 .  . 5 .. . .  8 . 9  . . .. . 8  . 6 .  4 . .3 . .  2 . .  . . .. 5 .  . . .  . 3 .. . 6  9 . .  2 . .7 . .  . . .  . . 1`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

I updated my solver to 2008-05-21
here are the results for center box included and center box ignored, respectively
the comment is the symmetry abbreviation and distance from that symmetry
Code: Select all
`sudoku -qFN -f'%#dc # %#D#sc' coloin.dat000009005030000070002080600008002400000640000100800000006900200070000010500000003 # d-3000000003006009200070020010000400000009006400500908000030000070002800600100000005 # p-5000001007030000050008020600000400900004602000800090000006040200070000001500000030 # d-3000000007002008600010040050000809000008060400300200000050000030006900200700000001 # p-4sudoku -qFN -f'%#cc # %#C#sc' coloin.dat000001005030000070002080600000608900008400000900020000006040200070000010500000003 # d-2000000003006009200070020010000400000009006400500908000030000070002800600100000005 # p-3000001007030000050008020600000400900004602000800090000006040200070000001500000030 # d-2000000007002008600010040050000809000008060400300200000050000030006900200700000001 # p-3`
Last edited by gsf on Thu May 22, 2008 1:52 am, edited 1 time in total.
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf wrote:here are the results for center box included
Code: Select all
`000009005030000070002080600008002400000640000100800000006900200070000010500000003 # d-6`

That was quick! This agrees with my manual result, but why do you count this as d-6 instead of d-3?
Code: Select all
` . . . | . . 9 | . . 5 . 3 . | . . . | . 7 . . . 2 | . 8 . | 6 . .-------+-------+------- . . 8 | . . 2 | 4 . . . . . | 6 4 . | . . . 1 . . | 8 . . | . . .-------+-------+------- . . 6 | 9 . . | 2 . . . 7 . | . . . | . 1 . 5 . . | . . . | . . 3 # d-6`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:That was quick! This agrees with my manual result, but why do you count this as d-6 instead of d-3?

counted too much -- will have to retune the inner loop
thanks
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

ronk wrote:That was quick! This agrees with my manual result, but why do you count this as d-6 instead of d-3?

fixed, post above edited to reflect the fix, and solver 2008-05-22 posted
thanks
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next