The New Sudoku Players' Forum

by **JPF** » Wed Apr 25, 2007 7:03 am

rep'nA wrote:
JPF wrote:As mentionned before, if A~A' and B~B' it can happen that d(A,B)<>d(A',B') but it doesn't matter.
JPF

Let f be an isomorphism of the grid sending A to A'. So we may write A' = f(A). Is it the case that d(A,B) = d(f(A), f(B))?

Again, in most cases that's not true.
See the examples already given before :

i wrote:Example :
Code: Select all
A : 500000009020100070008000300040600000000050000000207010003000800060004020900000005 m_b_metcalf B : 500000009020100070008000300040002000000050000000706010003000800060004020900000005 StrmCkr * * * *
d(A,B)= 4

using the gsf's canonical forms for these puzzles :
Code: Select all
A' : 000006000007180000000020005008500001300000900060000040002070008040000060900000300 B' : 100050000000089200000700000070000003006000040500002900004000060800010500030000007 * ** ** ** ** * *** ** * ** ** *** * * **** * ** ** * *
d(A',B')= 36

Of course if h is an automorphism of A, then A'=h(A)=A and
d(A,B)=d(h(A),B) for every B.

Mauricio wrote:I would think that a better definition of distance is this:

D(A,B)=min{d(A,B):A~A', B~B'}, using the d function defined by JPF.

In this new metric it is trivial that D(A,B)=D(A',B') if A~A' and B~B'. We would want this, as properties of sudokus besides aesthetics should be independent of isomorphism.

I think that's a good idea.

It has to be proved that D is a distance on the quotient set S/~

D(A,B)=0 then min{d(A',B'): A'~A, B'~B}=0.
so there are A' and B' such that d(A',B')=0 .
As d is a distance, A'=B' with A'~A and B'~B.
Finally A~B.

I don't have any proof (or counter example) that D(A,B)<=D(A,C)+D(C,B)
Any idea ?

JPF

by **re'born** » Wed Apr 25, 2007 11:40 am

JPF wrote:
rep'nA wrote:
JPF wrote:As mentionned before, if A~A' and B~B' it can happen that d(A,B)<>d(A',B') but it doesn't matter.
JPF

Let f be an isomorphism of the grid sending A to A'. So we may write A' = f(A). Is it the case that d(A,B) = d(f(A), f(B))?

Again, in most cases that's not true.
See the examples already given before :
i wrote:Example :
Code: Select all
A : 500000009020100070008000300040600000000050000000207010003000800060004020900000005 m_b_metcalf B : 500000009020100070008000300040002000000050000000706010003000800060004020900000005 StrmCkr * * * *
d(A,B)= 4

using the gsf's canonical forms for these puzzles :
[code]
A' : 000006000007180000000020005008500001300000900060000040002070008040000060900000300
B' : 100050000000089200000700000070000003006000040500002900004000060800010500030000007
* ** ** ** ** * *** ** * ** ** *** * * **** * ** ** * *

JPF

Unless I'm very confused about what is going on (an all too likely scenario) I don't think the above example is relevant to my question. I'm looking at the following situation: Transform a grid containing the pattern A (for instance, rotate the grid 180 degrees). This will give a new grid with a pattern A'. Now take another grid with pattern B. Apply the same transformation as we did to the grid containing A (rotation by 180 degrees). We will get a new grid with pattern B'. It is clear to me that (at least with rotations) d(A,B) = d(A',B').

In your example, you are allowing different transformations to be performed to get from A to A' and from B to B' (at least, I assume canonicalization will require different transformations). So it is unreasonable to hope that the distance should stay the same, but if we restrict ourselves to isomorphs obtained by the same transformations, it is possible that distance might be preserved. As I said above, I think rotations are clear. What isn't clear to me is what happens if you start messing with the numbers.

by **StrmCkr** » Wed Apr 25, 2007 7:56 pm

im wondering on something for some puzzles.

mostly the idea arived from looking at mine and M.M's puzzle.

as it is a puzzle that clearly shows my question/pondering.

as i have seen varitions like this exsit on other similar puzzels wher the diffrence is actualy a rotation symetry in side a box.

how the only variation between ours is a mirrored and fliped middle box

is it possible that a potential symetry was missed?

an inbox roational symetry??

take this puzzle for example.

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

it is not symetrical (can some one check ive done it by hand a few times and can't get it to go back)

to either of our puzzles but yet all i did was roate the 4 corners boxs in the same direction. 90 right.

...random thought for sudoku space.
distance and varition for degrees of symetries.
0= identncial, 1st degree is roational like mine and mm's. . 2nd being placement variations

where variation of numbers used between each for is the (0-3)^(number of diffrences)

.

by **coloin** » Thu Apr 26, 2007 9:51 am

I must admit I dont fully understand the clue mappings and "distance" between clues and whethr this stays the same in transformed puzzles......

suffice to say if we realy want to catagorize all puzzles in the sudoku space we might start [!] by considering this puzzle

Code: Select all: +---+---+---+ |1..|...|7..| |...|2..|...| |.59|...|3.2| +---+---+---+ |.4.|.8.|..7| |..6|95.|...| |...|..1|.6.| +---+---+---+ |..7|.3.|...| |...|5.8|1..| |36.|7.2|5.9| +---+---+---+ 26 clues minimal

fairly unremarkable except that there is [only] one set of 9 clues of this pattern in it

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

Not many puzzles have this full "attacking rook" template or RS 9/9. [Although I'm informed that all grids have an average of 200 of these] In significantly more puzzles the maximum you will find is a 8/9 pattern.

More commonly the maximum number of clues in this pattern in a puzzle is 7/9 clues.[There are two different types]

Code: Select all: xxx xxx xxx xx x or x x

Its fairly easy to sort out these 8/9 and 9/9 puzzles [one equivalent] but possibly more of an excercise to the many possible entwining combinations of 7/9 patterns. Can it be done ?

In some puzzles the maximum RS is a paultry 6 clues, very rarely there are 5...

C

by **JPF** » Thu Apr 26, 2007 11:08 am

rep'nA wrote:Let f be an isomorphism of the grid sending A to A'. So we may write A' = f(A). Is it the case that d(A,B) = d(f(A), f(B))?

rep'nA wrote:Unless I'm very confused about what is going on (an all too likely scenario) I don't think the above example is relevant to my question...

Sorry, I misread your post.

Ed Russell & Frazer Jarvis wrote:
The complete list of operations that we can perform is:
1. Relabel (i.e., permute) the 9 digits;
2. Permute the three stacks;
3. Permute the three bands;
4. Permute the three columns within a stack;
5. Permute the three rows within a band;
6. Any reflection or rotation.

and of course, any combinations of these operations.
Let's call such a combination a transformation (isomorphism) t of the grid G.
The resulting grid is tG.

It can easily be proved that for any puzzles A and B :

d(t(A), t(B))=d(A,B)

But, with 2 isomorphisms u,v :
d(u(A),v(B)) is not necessaraly equal to d(A,B).

and therefore A~A' and B~B' doesn't imply d(A,B)=d(A',B')

JPF

by **coloin** » Thu Apr 26, 2007 11:36 am

StrmCker
we rotated the corner boxes of our 16 clue templates - essentially combinations of rotations are equivalent - equivalent to a combination of row swaps - by swapping the clues in the corner boxes [eg r1c1 and r3c3] potentially a different template is made - giving sometimes up to 8 different templates.

Filling in a complete central box - and then removing unecessary clues was how we generated the batch of hard puzzles.......all looking fairly similar.

Code: Select all: +---+---+---+ |1..|...|..2| |.9.|4..|.5.| |..6|...|7..| +---+---+---+ |.5.|...|...| |...|...|...| |...|...|.4.| +---+---+---+ |7..|...|6..| |.3.|..9|.8.| |..2|...|..1| +---+---+---+ 1.......2.9.4...5...6...7...5.......................4...2...6...3...9.8.7.......1 - 676286 sol. 1.......2.9.4...5...6...7...5.......................4...7...6...3...9.8.2.......1 - 691248 sol. 6.......2.9.4...5...1...7...5.......................4...2...6...3...9.8.7.......1 - 708196 sol. 6.......2.9.4...5...1...7...5.......................4...7...6...3...9.8.2.......1 - 682164 sol. 1.......2.9.4...5...6...7...5.......................4.7.....6...3...9.8...2.....1 - 678104 sol. [Easter monster] 1.......7.9.4...5...6...2...5.......................4.7.....6...3...9.8...2.....1 - 696188 sol. 6.......2.9.4...5...1...7...5.......................4.2.....6...3...9.8...7.....1 - 688096 sol. 6.......2.9.4...5...1...7...5.......................4.7.....6...3...9.8...2.....1 - 685046 sol.

Your puzzle's template is the same as the original - 295376 sol.

It is isomorphic, 12 clues remaining the same. Essentilly all you have done is 2 row swaps and two relabels! 3=9 and 5=8

Code: Select all: +---+---+---+ |..5|...|3..| |.2.|1..|.7.| |8..|...|..9| +---+---+---+ |.4.|..2|...| |...|.5.|...| |...|7.6|.1.| +---+---+---+ |9..|...|..8| |.6.|..4|.2.| |..3|...|5..| +---+---+---+ +---+---+---+ |5..|...|..9| |.2.|1..|.7.| |..8|...|3..| +---+---+---+ |.4.|..2|...| |...|.5.|...| |...|7.6|.1.| +---+---+---+ |..3|...|8..| |.6.|..4|.2.| |9..|...|..5| +---+---+---+

Perhaps this would be a good example to show [it possibly might not be]

Code: Select all: and therefore A~A' and B~B' doesn't imply d(A,B)=d(A',B')

C

by **ravel** » Thu Apr 26, 2007 1:27 pm

Mauricio wrote:I would think that a better definition of distance is this:

D(A,B)=min{d(A,B):A~A', B~B'}, using the d function defined by JPF.

As i already stated, i agree with Mauricio, that equivalent puzzles should have distance 0, because they are essentially the same.
Additionally i think, we should distinguish pattern and clue distance. Then there are many ways, how we can define a minimum distance of puzzles A and B. The main problem is, how to calculate it, i suppose that it is a lot harder than to canonicalize (or normalize) puzzles.
E.g. we could
1. Get all equivalents B* with a maximum of common cells with A (without changing numbers)
2. Out of B* get those with maximum common givens (by changing numbers)
3. For the remaining calculate a distance with some formula using the number of needed number changes(same cell), cell changes (same number), number+cell changes and additions/removals of clues (if the number of givens is different for A and B)

by **re'born** » Thu Apr 26, 2007 1:54 pm

ravel wrote:
Mauricio wrote:I would think that a better definition of distance is this:

D(A,B)=min{d(A,B):A~A', B~B'}, using the d function defined by JPF.
As i already stated, i agree with Mauricio, that equivalent puzzles should have distance 0, because they are essentially the same.
Additionally i think, we should distinguish pattern and clue distance. Then there are many ways, how we can define a minimum distance of puzzles A and B. The main problem is, how to calculate it, i suppose that it is a lot harder than to canonicalize (or normalize) puzzles.

How about the following idea for distance:

Fix a canonicalized form. For any puzzle A, let c(A) denote its canonicalization. For puzzles A and B, define D(A,B) := d(c(A), c(B)) (with d(-,-) defined as above). Assuming that equivalent puzzles have the same canonical form, then this satisfies the requirement that equivalent puzzles should have distance distance 0. Also, unlike Mauricio's version, I think this should satisfy the triangle inequality and be an honest to goodness distance function.

by **JPF** » Thu Apr 26, 2007 2:53 pm

rep'nA wrote:How about the following idea for distance:

Fix a canonicalized form. For any puzzle A, let c(A) denote its canonicalization. For puzzles A and B, define D(A,B) := d(c(A), c(B)) (with d(-,-) defined as above). Assuming that equivalent puzzles have the same canonical form, then this satisfies the requirement that equivalent puzzles should have distance distance 0. Also, unlike Mauricio's version, I think this should satisfy the triangle inequality and be an honest to goodness distance function.

Yes, it's almost a distance :
D(A,B)>=0
D(A,B)=D(B,A)
D(A,B)<=D(A,C)+D(C,B)

but D(A,B) =0 iff A~B (not only A=B)

That is the concept proposed by m_b_metcalf at the begining of this thread.

Personnally, I was looking for a distance such that :
if B=Mut(A) ; ie=B differs from A in only one non empty cell
then D(B,A)=1

I'm not sure it's true with the minlex canonicalization.

JPF

by **ravel** » Thu Apr 26, 2007 2:53 pm

rep'nA wrote:How about the following idea for distance:

But now look at these puzzles in Gordon's normalization:

Code: Select all: 5.......1...7.9........3...46..5.......2..39.1..........3...72..1..6............. 5.......1...7.9........3...46..5.......2..39.1..........3...72..4..6............. 5.......1...7.9........3...46..5.......2..39.1..........3...72..8..4.............

And here is the gsf canonicalized form:

Code: Select all: .......89.5.1.............42.8.4..................53.....6.31.....5.....9.4....2. ...4......5.....36.....3.1.2.....9.......1.5.8.4.........9..8.....2..4...6....... 12.4..........93.6......5.......3..8.........74.....1.....1......5...9.....72....

So your distance between the same puzzles can differ very much, when using another normalization.

by **JPF** » Thu Apr 26, 2007 2:55 pm

ravel, thanks for the examples

JPF

by **tarek** » Thu Apr 26, 2007 3:48 pm

Hi guys,

I would favour a geometrical reference point. (This could be one of the puzzles or a hypothetical fully symmetrical puzzle with same number of clues)......
both puzzles are shuffled to match the geometry of the reference point (closest matching % of clues) then the distance is measured.

It is a bit complicated especially with non math terms that I'm using, but to me this seems the best way to tackle this.

tarek

by **re'born** » Fri Apr 27, 2007 11:06 am

JPF wrote:
rep'nA wrote:How about the following idea for distance:

Fix a canonicalized form. For any puzzle A, let c(A) denote its canonicalization. For puzzles A and B, define D(A,B) := d(c(A), c(B)) (with d(-,-) defined as above). Assuming that equivalent puzzles have the same canonical form, then this satisfies the requirement that equivalent puzzles should have distance distance 0. Also, unlike Mauricio's version, I think this should satisfy the triangle inequality and be an honest to goodness distance function.

Yes, it's almost a distance :
D(A,B)>=0
D(A,B)=D(B,A)
D(A,B)<=D(A,C)+D(C,B)

but D(A,B) =0 iff A~B (not only A=B)

Yes, of course. I was thinking (but not typing) of viewing everything in S/~, where it does become a distance function.

JPF wrote:That is the concept proposed by m_b_metcalf at the begining of this thread.

Ahh. I had not carefully read the first page.

ravel wrote:
rep'nA wrote:How about the following idea for distance:
But now look at these puzzles in Gordon's normalization:
Code: Select all
5.......1...7.9........3...46..5.......2..39.1..........3...72..1..6............. 5.......1...7.9........3...46..5.......2..39.1..........3...72..4..6............. 5.......1...7.9........3...46..5.......2..39.1..........3...72..8..4.............

And here is the gsf canonicalized form:
Code: Select all
.......89.5.1.............42.8.4..................53.....6.31.....5.....9.4....2. ...4......5.....36.....3.1.2.....9.......1.5.8.4.........9..8.....2..4...6....... 12.4..........93.6......5.......3..8.........74.....1.....1......5...9.....72....
So your distance between the same puzzles can differ very much, when using another normalization.

I'm not sure I see an inherent problem with that. If everybody uses the same normalization, then there isn't any problem at all. If we don't then it becomes a question of finding transformation laws that tell you how distances might change when you change the normalization.

Perhaps the real problem is that there is nothing canonical about our canonical forms.

by **ravel** » Fri Apr 27, 2007 1:11 pm

rep'nA wrote:I'm not sure I see an inherent problem with that. If everybody uses the same normalization, then there isn't any problem at all.

Hm, i have a problem with it. When i can transform 2 puzzles, so that they have the same pattern and only one number is different (twin sudokus), then i wish that a distance function would give the smallest possible nonzero value, e.g. 1., because 2 (non equivalent) puzzles cannot differ less in the givens.

Otherwise we have an abstract function, which might be well defined, but doesnt have any (intuitive) worth for me.

by **m_b_metcalf** » Fri Apr 27, 2007 1:55 pm

JPF wrote:metric space

You folks are doing splendid work on developing a metric. Does that mean we are getting close to having to consider n-dimensional cluster anlysis (and here) :?:

Regards,

Mike Metcalf

The New Sudoku Players' Forum

Sudoku space