The New Sudoku Players' Forum

[JPF]

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

[ronk]

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

[JPF]

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.

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

[Smythe Dakota]

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

[JPF]

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 :

• Sudoku Symmetry - Formalized
• Combinatorial Concepts with Sudoku. I : Symmetry
  

In my post, I was refering to those pattern-symmetries of order 2 (Type V, VI, VII in the Gordon's taxonomy).

JPF

[ronk]

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?

[JPF]

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

[tarek]

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

[JPF]

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

[tarek]

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

[gsf]

[ transferred from The Hardest Sudoku thread ]

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]

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


[ronk]

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

[gsf]

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]

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