JPF wrote:here Mauricio and I 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.

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

I'm still looking for a

smart proof that D is a

metric distance

or isn't

JPF

It is not hard.

d(A,B) is the hamming distance between A and B, as strings, it is easy to see that d is indeed a metric.

If f is a sudoku morphism (ie, some column, row, number permutations), denote f(A) the sudoku A after we apply the moves defined by f.

Now, D(A,B)=d(f(A),g(B)) for some sudoku morphisms f and g, and it is easy to see that d(f(A),g(B))=d(g^(-1)(f(A)),g^(-1)(g(B)))=d(g^(-1)(f(A)),B), where g^(-1) is the morphism inverse of g.

So D(A,B)=d(h(A),B) for some sudoku morphism h, and D(A,B)=d(A,k(B)) for some morphism k.

Now, D(A,C)+D(C,B)=d(h(A),C)+d(C,k(B))>=d(h(A),k(B))>=D(A,B). QED.