The best symmetry

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

The best symmetry

Postby JPF » Tue Dec 11, 2007 12:36 am

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: 3752
Joined: 06 December 2005
Location: Paris, France

Re: The best symmetry

Postby ronk » Tue Dec 11, 2007 2:47 am

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

Postby JPF » Tue Dec 11, 2007 11:24 pm

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
That's the right answer.

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: 3752
Joined: 06 December 2005
Location: Paris, France

Re: The best symmetry

Postby Smythe Dakota » Wed Dec 12, 2007 1:44 pm

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: 534
Joined: 11 February 2006

Postby JPF » Wed Dec 12, 2007 3:14 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby ronk » Wed Dec 12, 2007 11:30 pm

JPF wrote:That's the right answer.

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

Postby JPF » Thu Dec 13, 2007 7:49 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby tarek » Thu Dec 13, 2007 8:29 pm

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=81
2. remove  n clues from the puzzle
3. 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=n
6. if all possible combinations of n clues have been removed && S>1 then  goto 10
7. return the removed clues
8. n++
9. if n<C then goto 2
10. best symmetry is "S Modulo N"


tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby JPF » Thu Dec 13, 2007 8:51 pm

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=81

2. For each Q = isomorphic of P  [2* x 6^8 values]
3. For a symmetry s()    [ s = V, VI, VII ]
4. n=0
5. For each clue c of Q
6. if s(c) is not in Q then n=n+1
7. next c
8. if n<N then Sm=s and Qm=Q and N=n
9. next s
10. next Q

Best symmetry = Sm (modulo N), with puzzle Qm
* not sure if 2 is usefull or not (transposition)

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby tarek » Wed May 21, 2008 12:29 pm

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 Puzzle
2. M(absolute)=Po number of clues, S(absolute)=2 Ip(absolute)=Po
3. 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 S
6. 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) then
M(absolute)=M(x) S(absolute)=S Ip(absolute)=Ip(x) Sp(absolute)=Sp(x)


Maximal symmetry = Ip(absolute) symmetry
Modulo = M(absolute)


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

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby gsf » Wed May 21, 2008 5:37 pm

[ 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 .  . . .  . . 1
5 . .  . . .  . 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

Postby gsf » Wed May 21, 2008 6:17 pm

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.dat

000009005030000070002080600008002400000640000100800000006900200070000010500000003 # d-3
000000003006009200070020010000400000009006400500908000030000070002800600100000005 # p-5
000001007030000050008020600000400900004602000800090000006040200070000001500000030 # d-3
000000007002008600010040050000809000008060400300200000050000030006900200700000001 # p-4

sudoku -qFN -f'%#cc # %#C#sc' coloin.dat

000001005030000070002080600000608900008400000900020000006040200070000010500000003 # d-2
000000003006009200070020010000400000009006400500908000030000070002800600100000005 # p-3
000001007030000050008020600000400900004602000800090000006040200070000001500000030 # d-2
000000007002008600010040050000809000008060400300200000050000030006900200700000001 # 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

Postby ronk » Thu May 22, 2008 12:21 am

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

Postby gsf » Thu May 22, 2008 1:43 am

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

Postby gsf » Thu May 22, 2008 5:53 am

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

Return to General