The New Sudoku Players' Forum

[Addlan]

Hypothesis -- any Sudoku matrix can be transformed into any other Sudoku matrixes through swapping digits.

Verification: I have verified the hypothesis in 4*4 Sudoku matrix, however, I am not able to verify it in the normal 9*9 Sudoku matrix due to its complexity.

Swapping digits: after swapping some digits, a valid Sudoku matrix will still remain a valid Sudoku matrix.

Swapping digits happens when: 1. rotation (all digits swap with the digits against the centre point); 2. Swap columns/rows of boxes(such swapping the top three blocks with the middle three blocks); 3. Reflection (similar to No. 2 swap except the border between boxes acts as a mirror); 4. swapping rows or columns; 5. Renumbering (swapping all digits of any two like swapping all '1' and '2' digits); 6. Swapping digits along an open chain (discussed in detail below).

Some of the above contents come from Condor's:

http://forum.enjoysudoku.com/viewtopic.php?t=44&postdays=0&postorder=asc&start=210

Relationship between these swappings: 1. Rotation can be achieved by several boxes swapping; 2. reflection can be achieved by boxes swapping plus row/column swapping; 3. boxes swapping can be achieved by renumbering plus row/column swapping (still need to be proved strictly); 4. Renumbering and row/column swapping can be achieved by swapping along open chains.

Summary of relationship between swappings: there are three main kinds of swaps, they are boxes swapping, rows/columns swapping and swapping through opening chains. Because boxes swapping and rows/columns swapping are special cases of swapping though open chains, swappings can be divided into only two kinds of swapping: swapping through global open chain and swapping through local open chain -- shorten as open chain (will be discussed in details below).

Swapping through (local) open chains: when two different digits in two grids are swapped, by swapping these two digits in other grids, it will remain a valid Sudoku matrix. It forms a kind of chain and that is where its name comes from. More than two digits chain: if an opening chain (must be local chain) involves more than two digits, it can be divided into several two digits chain. I have found a few examples of this, however, I am not 100% sure because it stil needs a strict proof.

Take Condor's Sudoku Queen which is recently discussed in the forum as an example below:

453|671|928
921|853|674
876|249|153
-----------
594|182|367
162|397|485
387|465|291
-----------
715|924|836
238|716|549
649|538|712

If we look at block 1 at the left upper corner. If we swap digit '1' and '2' there, it will take 3 swaps, 8 digits involved (length=4) to remain a valid Sudoku matrix which is shown below. The rest of '1' and '2' form another local chain. However, if we swap r2c2 = 2 and r4c4 = 1, all digits of '1' and '2' must swap in order to remain valid because they are taken from different chains.

453|671|928
912|853|674
876|249|153
-----------
594|182|367
261|397|485
387|465|291
-----------
725|914|836
138|726|549
649|538|712

If you try all digits in block 1, you will find that most of the digits need 18 digits involved (8 swaps). The length of the chain varies from 2 to 9. If you find a length=x, the rest of the digits will form another chain with length = 9-x. Because swapping won't destroy any chains in either global or local level, so according to the hypothesis, all Sudoku matrixes will have same number and same kinds of local chains. I don't have time to verify this yet, it is very time consuming by hand. If someone is able to prove a few examples by programming, that will be great. If not true, then my hypothesis about Sudoku matrix must be wrong.

Some possible conclusion of the hypothesis:
Uniqueness = when no open chains exist = only have close chains (which needs to involve the swap with hints)
If a Sudoku matrix can be transformed so that it coincides with the hints of another Sudoku matrix, the transformed Sudoku must be the solution to the hints, i.e. equal to the Sudoku needs to be found out.

There are still many questions remained. And I hope the above will help to explore more about Sudoku matrix.

[frazer]

I think I'm sceptical about your hypothesis, but I don't feel confident in my scepticism! I've seen your 4x4 result somewhere else (on the Sudoku programmers board, if I remember correctly) - I remember being impressed.

Restricting to operations 1--5, Red Ed and I showed that there are 5472730538 different grids. But the chain operation (6) looks very powerful, and surely reduces this number by a large factor. When Bertram and I worked out the total number of grids, we started by working out all of the 3x9 top three rows. With the operations 1--5, there are 416 different arrangements; we then incorporated a limited form of (6) and got the number down to 71, and subsequently Red Ed got this down to 44, using the full force of (6). Of course, extending this to 9x9 could give rather different results, and it's possible that the extra chains you get then really do allow you to transform every grid into any other. I'll think about it too, if I get time.

[dukuso]

I'm pretty sure that the hypothesis is wrong.
Operation 6 does reduce the classes a lot, but there
still remain another lot.
Operations 1-5 don't change the chain-structure, so if the hypothesis
were true, then there were only one chain-structure !
But I already found hundreds. I remember I computed the
chain-structures of Gordon Royle's 17-clue-sudokus
and rarely two of them had the same chain-structure.
I have a C-program which
given a sudoku-matrix prints its chain-structure-encoding.
I can send it, if anyone is interested.


Guenter.

[Addlan]

I think I'm sceptical about your hypothesis, but I don't feel confident in my scepticism! I've seen your 4x4 result somewhere else (on the Sudoku programmers board, if I remember correctly) - I remember being impressed.

I haven't shown my 4*4 result in this forum yet. I drew all of them by hand on papers and I restrict the first block to '1 2 3 4'. I list all the possiblilities and prove that each one can be transformed into any others.

Restricting to operations 1--5, Red Ed and I showed that there are 5472730538 different grids. But the chain operation (6) looks very powerful, and surely reduces this number by a large factor. When Bertram and I worked out the total number of grids, we started by working out all of the 3x9 top three rows. With the operations 1--5, there are 416 different arrangements; we then incorporated a limited form of (6) and got the number down to 71, and subsequently Red Ed got this down to 44, using the full force of (6). Of course, extending this to 9x9 could give rather different results, and it's possible that the extra chains you get then really do allow you to transform every grid into any other. I'll think about it too, if I get time.

The transform surely is very complicated, to understand it is one matter, to use it is another. I will think about it in my spare time. It is a very time consuming and need lots of people's efforts.

[Addlan]

I'm pretty sure that the hypothesis is wrong.
Operation 6 does reduce the classes a lot, but there
still remain another lot.
Operations 1-5 don't change the chain-structure, so if the hypothesis
were true, then there were only one chain-structure !
But I already found hundreds. I remember I computed the
chain-structures of Gordon Royle's 17-clue-sudokus
and rarely two of them had the same chain-structure.
I have a C-program which
given a sudoku-matrix prints its chain-structure-encoding.
I can send it, if anyone is interested.

I am interested in the program, could you please send the program to me? It seems to me all operations don't change the chain structure. How about examining all chains between A and B? A,B -- digit 1-9. And it seems to me any two digits form two separate chains, but I haven't examined this yet.

[Nick70]

I haven't shown my 4*4 result in this forum yet. I drew all of them by hand on papers and I restrict the first block to '1 2 3 4'. I list all the possiblilities and prove that each one can be transformed into any others.

Maybe Frazer was thinking of this post.

Here I show that there are only two different 4x4 grids:

1234 1234
3412 3421
2143 2143
4321 4312

once you've done that, you just need to notice that they are the same except for the 1-2 cycle.

[dukuso]

I have a C-program which
given a sudoku-matrix prints its chain-structure-encoding.
I can send it, if anyone is interested.

I am interested in the program, could you please send the program to me? It seems to me all operations don't change the chain structure. How about examining all chains between A and B? A,B -- digit 1-9. And it seems to me any two digits form two separate chains, but I haven't examined this yet.

I uploaded the executable to http://magictour.free.fr/nppcs2.exe
C-source-code is attached to the executable.
Here it is again:


// cycle-lengths-signature of a sudoku
// assumes valid sudoku grids in file, else might crash
// symbols other than 1,2,3,4,5,6,7,8,9 are ignored

#include <stdio.h>
int a,s,f,i,j,k,n,m,z,q,q1,t,x,y;
int S[88],X[88],Y[88],B[8][88],U[888],V[99][88],Z[9][9],T[8888];
char c[88];
long long Node[9],nodes=0;
FILE *file;

int main(int argc,char*argv[]){
T[9]=1;T[27]=2;T[72]=2;T[36]=3;T[63]=3;T[45]=4;T[54]=4;
T[225]=5;T[252]=5;T[522]=5;
T[234]=6;T[243]=6;T[324]=6;T[342]=6;T[423]=6;T[432]=6;T[333]=7;
T[2223]=8;T[2232]=8;T[2322]=8;T[3222]=8;

if(argc<2){printf("\n\nusage:nppcs file \n\n prints the chain-length-signiature of a sudoku\n\n file contains valid 9*9-sudoku-grids,\n symbols other than 1,2,3,4,5,6,7,8,9 are ignored\n");
printf("\n\n codes of the chain-lengths are:\n1:9\n2:2+7\n3:3+6\n4:4+5\n5:2+2+5\n6:2+3+4\n7:3+3+3\n8:2+2+2+3\n");

exit(1);}

if((file=fopen(argv[1],"rt"))==NULL){printf("file-error");exit(1);}

m1t:
for(i=0;i<9;i++)for(j=0;j<9;j++){
m3e:a=fgetc(file);
if(feof(file)){fclose(file);exit(1);}
if(a<49 || a>57)goto m3e;
V[i][j]=a-49;
}


// for(i=0;i<9;i++)for(j=0;j<9;j++)printf("%i",argv[1][i*9+j]-48);
// for(i=0;i<9;i++){for(j=0;j<9;j++)printf("%i ",V[i][j]);printf("\n");}exit(1);


for(i=0;i<9;i++){
for(j=0;j<9;j++)Z[i][j]=0;
for(j=0;j<9;j++){m=1;z=0;if(i==j)goto m76;

for(k=0;k<9;k++)U[k]=0;
for(k=0;k<9;k++){X[k]=0;while(V[k][X[k]]!=i)X[k]++;}
for(k=0;k<9;k++){Y[k]=0;while(V[Y[k]][k]!=j)Y[k]++;}

f=0;m2:while(U[f]>0 && f<9)f++;if(f>8)goto m6;
k=0;x=f;m1:k++;y=X[x];x=Y[y];U[x]=1;if(x!=f)goto m1;
z+=k*m;m*=10;
f++;goto m2;

m6:; Z[i][T[z]]++;

m76:;} // next j

m=1;s=0;for(j=8;j>0;j--){s+=Z[i][j]*m;m*=10;}S[i]=s;

} // next i

for(i=0;i<9;i++)for(j=i+1;j<9;j++)if(S[i]>S[j]){s=S[i];S[i]=S[j];S[j]=s;}

for(i=0;i<9;i++)printf("%08i ",S[i]);printf("\n");

//printf("9 27 36 45 225 234 333 2223\n");

goto m1t;

}

[Addlan]

Maybe Frazer was thinking of this post.

Here I show that there are only two different 4x4 grids:

1234 1234
3412 3421
2143 2143
4321 4312

once you've done that, you just need to notice that they are the same except for the 1-2 cycle.

It was done in a more smarter way than I did. I have 12 different 4*4 grids and reduce them to one with all operations.

[Addlan]

I uploaded the executable to http://magictour.free.fr/nppcs2.exe
C-source-code is attached to the executable.
Here it is again:

Thanks for the program, Dukuso. I am doubting if the chain structure is really what we expect. I mean the length of a chain may be described as a kind of chain or something. It will be nice if you can describe how you define a chain structure of Sudoku. I wonder how many separate chains are there in a Sudoku -- those chains whose length is less than 9.

[sciguy47]

If you're intrested, you can check out my topic called "Hear Me Out".