gfroyle wrote:Ocean wrote:Any sudoku can be transformed to one of its normalized forms through a permutation matrix P, and back again with the 'inverse' of P (denoted P^).

I don't believe this...

The norms themselves are all perfectly sensible, but the representation of the transformation from a sudoku to its norm doesn't seem right to me, because a single matrix cannot represent all of the operations of row-permutation, column-permutation, symbol relabelling and transposition.

Thank you for the corrections! It was obviously wrong to call the transformation a 'permutation matrix', since that concept has a precise mathematical meaning.

What I actually meant, was: It's possible to define a transformation operator P, and the related transformation operation P*A (NOT matrix multiplication). I think the operator P can be represented as three 9-element vectors R,C and V (all some specific permutation of 123456789), plus a number T (0 or 1). (The transformation operation consists of one row permutation, one column permutation, one symbol relabelling, and possibly one transposition).

If the operation i linear (and I believe it is) it is possible to define the corresponding inverse operation (and the inverse operator P^).

Hope I didn't go too wrong here - I have not written the algorithms yet or carried out any formal proofs, only done some 'back of the envelope' calculations...

PS.

Just a small comment on 'symbol relabelling': The vector V might be hard to FIND, but is simple to USE: Apply the unix command "tr" directly on a file, or a C-statement like "for (i=1;i<=81;i++) B[i]=V[A[i]];".

PPS.

- -Here are the ideas developed so far ...

Let the transformation operator P be represented by the set of three 9x9 permutation matrices R, C and V, plus a possible transposition t. [As a convention we say t=0 means no transpose, and t=1 means transpose].

P = {R; C; V; t}

For two consecutive transformations P1 and P2, we define the product P1 * P2:

P1 = {R1; C1; V1; t1}

P2 = {R2; C2; V2; t2}

P1 * P2 = {R1[(1-t1)R2+t1C2]; [(1-t1)C2+t1R2]C1; V1*V2; (t1+t2)mod 2}

If the transformation operation is linear, it's possible to define an inverse operator P^, such that P * P^ = {I; I; I; 0}, where I denotes the identity matrix.

P^ = {(1-t)R^+tC^; (1-t)C^+tR^; V^; t}

(where R^,C^,V^ denotes the respective inverse matrices).

... hope most of it is correct so far. The noncommutativity of the transformation operation (and matrix operations) might not have been taken proper care of...

If we represent the permutation matrices by their corresponding array representation:

For V, all 9! possible permutations of 123456789 are allowed (362880).

For R and C, only 6^4 (=1296) combinations of 123456789 are allowed.

!--------------------------------

The whole point of all this, was...

Conjecture:

Any two sudokus A1 and A2 belonging to the same class can be transformed to some common instance of the class (for example a chosen normalized form). If the transformation to this norm is represented by operators P1 and P1, the transformation between A1 and A2 is P1 * P2^:

P1 * P2^ = {R1[(1-t1)((1-t2)R2^+t2C2^)+t1((1-t2)C2^+t2R2^)]; [(1-t1)((1-t2)C2^+t2R2^)+t1((1-t2)R2^+t2C2^)]C1; V1*V2^; (t1+t2)mod 2}

The four cases for t1/t2 gives:

t1=0, t2=0 =>: P1 * P2^ = {R1*R2^; C2^*C1; V1*V2^; 0}

t1=0, t2=1 =>: P1 * P2^ = {R1*C2^; R2^*C1; V1*V2^; 1}

t1=1, t2=0 =>: P1 * P2^ = {R1*C2^; R2^*C1; V1*V2^; 1}

t1=1, t2=1 =>: P1 * P2^ = {R1*R2^; C2^*C1; V1*V2^; 0}

!-----------------