Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

short and fast sudoku-generator in C
Goto page 1, 2, 3, 4  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Sep 03, 2005 8:23 pm    Post subject: short and fast sudoku-generator in C Reply with quote
Code:


/* short and fast sudoku-generator in C, compiled with gcc3.2
executable at http://magictour.free.fr/suexg.exe
 repost bugs,improvement-suggestions to sterten@aol.com
 for some explanation of the solver
http://magictour.free.fr/suexco.txt
generates about 13 almost random sudokus per second with 1 GHz
by starting from an empty grid,
starting from a full grid is about 4 times faster
the generated sudokus are locally minimal, so removing
any clue results in a puzzle with multiple solutions
this program is public domain
*/

#include <stdio.h>
#define MWC (   (zr=36969*(zr&65535)+(zr>>16))   ^   (wr=18000*(wr&65535)+(wr>>16))   )
unsigned zr=362436069, wr=521288629;

int Rows[325],Cols[730],Row[325][10],Col[730][5],Ur[730],Uc[325],V[325];
int P[88],A[88],C[88],I[88];
int s1,m0,c1,c2,r1,l,i1,m1,m2,a,p,i,j,k,r,c,d,n=729,m=324,x,y,s;
int seed,solutions,min,clues,match;
char L[11]=".123456789";

int solve();


int main(int argc,char*argv[]){
  if(argc<2){printf("\nusage:suexg seed\n\n    generates locally minimal sudokus\n");exit(1);}
  sscanf(argv[1],"%i",&seed);zr^=seed;wr+=seed;

r=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++)for(s=1;s<=9;s++){
r++;Cols[r]=4;Col[r][1]=x*9-9+y;Col[r][2]=(3*((x-1)/3)+(y-1)/3)*9+s+81;
Col[r][3]=x*9-9+s+81*2;Col[r][4]=y*9-9+s+81*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
a=Col[r][c];Rows[a]++;Row[a][Rows[a]]=r;}

m0: for(i=1;i<=81;i++)A[i]=0;
mr1:i1=(MWC>>8)&127;if(i1>80)goto mr1;i1++;if(A[i1])goto mr1;
mr3:s=(MWC>>9)&15;if(s>8)goto mr3;s++;
    A[i1]=s;m2=solve();
    if(m2<1)A[i1]=0;if(m2!=1)goto mr1;

for(i=1;i<=81;i++){mr4:x=(MWC>>8)&127;if(x>=i)goto mr4;x++;P[i]=P[x];P[x]=i;}
for(i1=1;i1<=81;i1++){s1=A[P[i1]];A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

for(i=1;i<=81;i++)printf("%c",L[A[i]]);printf("\n");
goto m0;
return 0;}



int solve(){
   for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
   clues=0;for(i=1;i<=81;i++)
     if(A[i]){clues++;r=i*9-9+A[i];
       for(j=1;j<=Cols[r];j++){d=Col[r][j];if(Uc[d])return 0;Uc[d]++;
         for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}}}
   for(c=1;c<=m;c++){V[c]=0;for(r=1;r<=Rows[c];r++)if(Ur[Row[c][r]]==0)V[c]++;}

   i=clues;m0=0;m1=0;solutions=0;
m2:i++;I[i]=0;min=n+1;if(i>81 || m0)goto m4;
   if(m1){C[i]=m1;goto m3;}
   for(c=1;c<=m;c++)if(!Uc[c]){if(V[c]<=min)c1=c;
     if(V[c]<min){min=V[c];C[i]=c;if(min<2)goto m3;}}
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
   r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;m1=0;
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];
      for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;if(Ur[r1]==1)
         for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]--;
            if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2)m1=c2;}}}
   if(i==81)solutions++;if(solutions>1)goto m9;goto m2;
m4:i--;c=C[i];r=Row[c][I[i]];if(i==clues)goto m9;
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]--;
      for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]--;
         if(Ur[r1]==0)for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]++;}}}
   if(i>clues)goto m3;
m9:return solutions;}


Last edited by dukuso on Mon Oct 03, 2005 2:48 pm; edited 2 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Misza

Joined: 14 Sep 2005
Posts: 1
:

Items
PostPosted: Wed Sep 14, 2005 7:04 pm    Post subject: Nice Reply with quote
Nice code. Have you considered entering the International Obfuscated C Contest? Or is that you entry into it? Wink
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Sep 14, 2005 7:18 pm    Post subject: Reply with quote
well, I like when it can be printed on one page.
But I'm not trying to obfuscate it.
Sorry, if you feel so.
OK, if there is demand, I'll add some comments
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Sun Oct 02, 2005 6:23 pm    Post subject: Reply with quote
Could you explain how to run your .exe?

Specifically, what is the 'seed'? The only sudoku's i have managed to generate have been unsolvable by logic so far.

Thanks!
Back to top
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Oct 02, 2005 7:18 pm    Post subject: Reply with quote
the seed initializes the random generator.
Same seed - same sudokus.
About 50% of the generated sudokus should be solvable with
naked single/hidden single alone.
Here is a new version :

Code:

char G[9999]="

   suexg version 12, small randomized sudoku-generator in C,

   generates about 24 sudokus per second with 1GHz
   based on an exact cover solver, compiled with gcc3.2
   Report bugs,improvement suggestions,feedback to sterten@aol.com
   For some explanation of the solver see: http://magictour.free.fr/suexco.txt
   This generator starts from an empty grid and adds clues completely at random
   There are faster pseudo-random methods which generate upto 1000 sudokus
   per second.
   For a solver see: http://magictour.free.fr/suexk.exe
     (C-sourcecode is attached to the executable )
   Send sudokus with rating more than 100000 to sterten@aol.com
   so they can be included in the list of hardest sudokus at
   http://magictour.free.fr/top94

   You can download a DOS/Windows executable of this program from
   http://magictour.free.fr/suexg.exe


   This software is public domain
";






#include <stdio.h>
#define MWC ((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)))

unsigned zr=362436069, wr=521288629;
int Rows[325],Cols[730],Row[325][10],Col[730][5],Ur[730],Uc[325],V[325],W[325];
int P[88],A[88],C[88],I[88],Two[888];
// char B[83]="0111155555135559999135999888133947778113946678333442678344422678442226678222666778";
char B[83]="0111222333111222333111222333444555666444555666444555666777888999777888999777888999";
int w,f,s1,m0,c1,c2,r1,l,i1,m1,m2,a,p,i,j,k,r,c,d,n=729,m=324,x,y,s;
int q7,part,nt,rate,nodes,seed,solutions,min,samples,sam1,clues;
char L[11]=".123456789";
FILE *file;

int solve();

//------------------------------------------------------------
int main(int argc,char*argv[]){
  if(argc<2){printf("\nusage:suexg random-seed [z] [with rating] \n\n");
       printf("     generates z locally minimal sudokus [and rates them]\n");
       printf("     use different numbers for seed to get different streams of sudokus\n");
       printf("     default is : z=1e9 and without rating   [if these are not specified]\n");
       printf("     to redirect the sudokus to a file use e.g. : suexg 0 100 r >file\n");
       printf("\n     suexg i  : printf more info\n     \n");
       exit(1);}
  sscanf(argv[1],"%i",&seed);zr^=seed;wr+=seed;
  samples=1000000000;if(argc>2)sscanf(argv[2],"%i",&samples);
  rate=0;if(argc>3)rate=1;
  if(argv[1][0]=='i'){printf("%s",G);exit(0);}

for(i=0;i<888;i++){j=1;while(j<=i)j+=j;Two[i]=j-1;}

r=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++)for(s=1;s<=9;s++){
r++;Cols[r]=4;Col[r][1]=x*9-9+y;Col[r][2]=(B[x*9-9+y]-48)*9-9+s+81;
Col[r][3]=x*9-9+s+81*2;Col[r][4]=y*9-9+s+81*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
a=Col[r][c];Rows[a]++;Row[a][Rows[a]]=r;}

    sam1=0;
m0s:sam1++;if(sam1>samples)exit(0);

m0: for(i=1;i<=81;i++)A[i]=0;part=0;q7=0;
mr1:i1=(MWC>>8)&127;if(i1>80)goto mr1;i1++;if(A[i1])goto mr1;
mr3:s=(MWC>>9)&15;if(s>8)goto mr3;s++;   
    A[i1]=s;m2=solve();q7++;//if(q7>999)goto m0;
// add a random clue and solve it. No solution ==> remove it again.
// Not yet a unique solution ==> continue adding clues
    if(m2<1)A[i1]=0;if(m2!=1)goto mr1;

//now we have a unique-solution sudoku. Now remove clues to make it minimal
part++;if(solve()!=1)goto m0;
for(i=1;i<=81;i++){mr4:x=(MWC>>8)&127;if(x>=i)goto mr4;x++;P[i]=P[x];P[x]=i;}
for(i1=1;i1<=81;i1++){s1=A[P[i1]];A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

if(rate){nt=0;for(f=0;f<100;f++){solve();nt+=nodes;}printf("rating:%6i , ",nt);}
for(i=1;i<=81;i++)printf("%c",L[A[i]]);printf("\n");
goto m0s;}


//-----------------------------------------------------------------------
int solve(){//returns 0 (no solution), 1 (unique sol.), 2 (more than one sol.)
   for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
   clues=0;for(i=1;i<=81;i++)
     if(A[i]){clues++;r=i*9-9+A[i];
       for(j=1;j<=Cols[r];j++){d=Col[r][j];if(Uc[d])return 0;Uc[d]++;
         for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}}}
   for(c=1;c<=m;c++){V[c]=0;for(r=1;r<=Rows[c];r++)if(Ur[Row[c][r]]==0)V[c]++;}

   i=clues;m0=0;m1=0;solutions=0;nodes=0;
m2:i++;I[i]=0;min=n+1;if(i>81 || m0)goto m4;
   if(m1){C[i]=m1;goto m3;}
   w=0;for(c=1;c<=m;c++)if(!Uc[c]) {  if(V[c]<2){C[i]=c;goto m3;}
          if(V[c]<=min){w++;W[w]=c;};
          if(V[c]<min){w=1;W[w]=c;min=V[c];} }
mr:c2=MWC&Two[w];if(c2>=w)goto mr;C[i]=W[c2+1];
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
   r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;m1=0;
   nodes++;//if(nodes>9999 && part==0)return 0;
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];
      for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;if(Ur[r1]==1)
         for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]--;
            if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2)m1=c2;}}}
   if(i==81)solutions++;if(solutions>1)goto m9;goto m2;
m4:i--;c=C[i];r=Row[c][I[i]];if(i==clues)goto m9;
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]--;
      for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]--;
         if(Ur[r1]==0)for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]++;}}}
   if(i>clues)goto m3;
m9:return solutions;}

Back to top
View user's profile Send private message Send e-mail Visit poster's website
Paul

Joined: 11 Aug 2005
Posts: 29
:

Items
PostPosted: Wed Oct 19, 2005 2:55 pm    Post subject: Reply with quote
Thanks, have now got this working.

Very fast, and i like the fact it can output to a file. The only improvement i can see would be to add symmetry (but that's just a personal preference).

Cheers,
Paul
Back to top
View user's profile Send private message Visit poster's website
fmr

Joined: 13 Dec 2005
Posts: 1
:

Items
PostPosted: Tue Dec 13, 2005 3:42 pm    Post subject: Reply with quote
In this piece of code:
dukuso wrote:
for(i1=1;i1<=81;i1++){s1=A[P[i1]];A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

I changed it to:
Code:
for(i1=1;i1<=81;i1++){s1=A[P[i1]];if( !s1 ) continue; A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

This avoids solving a grid where you replace a 0 (no clue) by another 0. I gained about 40% increase in speed. Is there anything wrong by doing this ? I know the solver uses the random generator (MWC) to solve the grids, so by doing this I'm likely to change the resulting grids.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Dec 14, 2005 12:48 am    Post subject: Reply with quote
fmr wrote:
In this piece of code:
dukuso wrote:
for(i1=1;i1<=81;i1++){s1=A[P[i1]];A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

I changed it to:
Code:
for(i1=1;i1<=81;i1++){s1=A[P[i1]];if( !s1 ) continue; A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

This avoids solving a grid where you replace a 0 (no clue) by another 0. I gained about 40% increase in speed. Is there anything wrong by doing this ? I know the solver uses the random generator (MWC) to solve the grids, so by doing this I'm likely to change the resulting grids.


that's OK. In other versions I do this checking too.
Speed was not so much an issue here.
It was in the 16*16 version, which should be somewhere here too.
Bo had optimized it
Back to top
View user's profile Send private message Send e-mail Visit poster's website
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 2:01 pm    Post subject: Reply with quote
hi dukuso,
Can you tell me what MWC is used for? Is it part of generating random numbers? I do the math manually and I get MWC=1.

Also, what does bitwise shift right on MWC and 8 & 127 do?

Code:
#define MWC ((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)))

i1=(MWC>>8)&127
Back to top
View user's profile Send private message
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Thu Dec 15, 2005 8:50 pm    Post subject: Reply with quote
Quote:
I know the solver uses the random generator (MWC) to solve the grids, so by doing this I'm likely to change the resulting grids.


Ok...I see that MWC *is* the random generator. Embarassed

On that note what are the constraints of i1=(MWC>>8)&127?

Between what 2 numbers will the random number fall?

KW
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Dec 16, 2005 5:50 pm    Post subject: Reply with quote
King Wonka wrote:
Quote:
I know the solver uses the random generator (MWC) to solve the grids, so by doing this I'm likely to change the resulting grids.


Ok...I see that MWC *is* the random generator. :oops:

On that note what are the constraints of i1=(MWC>>8)&127?

Between what 2 numbers will the random number fall?

KW


0 and 127.
The ">>8" is maybe not necessary. Just to make it more random.
You can replace MWC with another random number generator
Back to top
View user's profile Send private message Send e-mail Visit poster's website
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Sat Dec 17, 2005 2:08 am    Post subject: Reply with quote
dukuso,
I'm still studying this code and I've found why it's not compiling for me. This line:
Code:
Col[r][2]=(B[x*9-9+y]-48)*9-9+s+81

It appears you're subtracting 48 from a string. That's where my error is coming from. Is there a substitue I can use instead that doesn't do that?
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sat Dec 17, 2005 5:35 am    Post subject: Reply with quote
King Wonka wrote:
It appears you're subtracting 48 from a string. That's where my error is coming from.

You're evidently using a good compiler - one which type checks variables. Anyhow, you can safely cast the offending char to an int here as dukuso appears to be using the ordinal value of that char.
Back to top
View user's profile Send private message Visit poster's website
King Wonka

Joined: 14 Dec 2005
Posts: 26
:

Items
PostPosted: Sat Dec 17, 2005 6:23 am    Post subject: Reply with quote
Ok I converted the:
Code:
B[x*9-9+y]

to an integer and how I'm getting a negative answer and an out of arrary error. Answer was like -359 if memory serves. I plugged in the old formula from the first version in this thread and it seems to be working. Still would like to figure out the ordinal thing though.

Anthony
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Dec 17, 2005 7:00 am    Post subject: Reply with quote
hi Anthony,

what compiler are you using ? I use gcc3.2 and there are no problems.
Others compiled it as well.
The B[] array is not meant as a string but as an array of integers.
It's just easier to enter them as a string.
You could replace the line :

char B[83]="011....
by:
int B[83]={48,49,49,...
just the ASCII-codes.


below is a more recent version:

Code:


//option to generate several sudokus starting from the same random grid
//head-message as C-comment, printing it as with 's'-option


char G[9999]="

   suexg version 16, Oct.29.2005
   randomized,public-domain sudoku-generator with C-sourcecode,

   generates about 24 sudokus per second with 1GHz
   based on an exact cover solver, compiled with gcc3.2
   Report bugs,improvement suggestions,feedback to sterten@aol.com
   For some explanation of the solver see: http://magictour.free.fr/suexco.txt
   This generator starts from an empty grid and adds clues completely at random
   There are faster pseudo-random methods which generate upto 1000 sudokus
   per second.
   For a solver see: http://magictour.free.fr/suexk.exe
     (C-sourcecode is attached to the executable )
   Send feedback to sterten@aol.com
   You can download a DOS/Windows executable of this program from
   http://magictour.free.fr/suexg.exe


   This software is public domain
";






#include <stdio.h>
#define MWC ((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)))

unsigned zr=362436069, wr=521288629;
int Rows[325],Cols[730],Row[325][10],Col[730][5],Ur[730],Uc[325],V[325],W[325];
int P[88],A[88],A0[88],C[88],I[88],Two[888];
// char B[83]="0111155555135559999135999888133947778113946678333442678344422678442226678222666778";
char B[83]="0111222333111222333111222333444555666444555666444555666777888999777888999777888999";
char H[326][7];
int b,w,f,s1,m0,c1,c2,r1,l,i1,m1,m2,a,p,i,j,k,r,c,d,n=729,m=324,x,y,s;
int mi1,mi2,q7,part,nt,rate,nodes,seed,solutions,min,samples,sam1,clues;
char L[99]=".123456789";
FILE *file;

int solve();

//------------------------------------------------------------
int main(int argc,char*argv[]){
  if(argc<2){printf("\nusage:suexg random-seed [z] [file] [with rating] \n\n");
       printf("     generates z locally minimal sudokus [and rates them]\n");
       printf("     use different numbers for seed to get different streams of sudokus\n");
       printf("     default is : z=1e9 and without rating   [if these are not specified]\n");
       printf("     if file is given then for each puzzle in file z random sudokus are given\n");
       printf("       by starting from the given puzzle rather than from an empty grid\n");
       printf("     to redirect the sudokus to a file use e.g. : suexg 0 100 r >file\n");
       printf("\n     suexg i  : printf more info\n     suexg s  : prints source-code\n");
       exit(1);}
  sscanf(argv[1],"%i",&seed);zr^=seed;wr+=seed;
  samples=1000000000;if(argc>2)sscanf(argv[2],"%i",&samples);
  rate=0;if(argc>3)rate=1;if(argc>4)rate=2;
  if(argv[1][0]=='i'){printf("%s",G);exit(0);}
  if(argv[1][0]=='s'){if((file=fopen(argv[0],"rb"))==NULL)
                        {printf("\ncan't find suexg.exe\n");exit(1);}
      ip1:w=0;for(i=1;i<33;i++)w+=(fgetc(file)==45);if(w<32)goto ip1;
      while(fgetc(file)!='_');
      ip2:x=fgetc(file);if(x!=13)printf("%c",x);if(feof(file))exit(1);goto ip2;}


  if(argv[3][0]>'9')rate=0;
  if(argv[3][0]>'9')if((file=fopen(argv[3],"rb"))==NULL)
                        {printf("\ncan't find file %s\n",argv[3]);exit(1);}

for(i=0;i<888;i++){j=1;while(j<=i)j+=j;Two[i]=j-1;}
for(i=1;i<=81;i++)A0[i]=0;

r=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++)for(s=1;s<=9;s++){
r++;Cols[r]=4;Col[r][1]=x*9-9+y;Col[r][2]=(B[x*9-9+y]-48)*9-9+s+81;
Col[r][3]=x*9-9+s+81*2;Col[r][4]=y*9-9+s+81*3;}
for(c=1;c<=m;c++)Rows[c]=0;
for(r=1;r<=n;r++)for(c=1;c<=Cols[r];c++){
a=Col[r][c];Rows[a]++;Row[a][Rows[a]]=r;}

c=0;for(x=1;x<=9;x++)for(y=1;y<=9;y++){c++;H[c][0]='r';H[c][1]=x+48;H[c][2]='c';H[c][3]=y+48;H[c][4]=0;}
c=81;for(b=1;b<=9;b++)for(s=1;s<=9;s++){c++;H[c][0]='b';H[c][1]=b+48;H[c][2]='s';H[c][3]=s+48;H[c][4]=0;}
c=81*2;for(x=1;x<=9;x++)for(s=1;s<=9;s++){c++;H[c][0]='r';H[c][1]=x+48;H[c][2]='s';H[c][3]=s+48;H[c][4]=0;}
c=81*3;for(y=1;y<=9;y++)for(s=1;s<=9;s++){c++;H[c][0]='c';H[c][1]=y+48;H[c][2]='s';H[c][3]=s+48;H[c][4]=0;}


m6:if(argv[3][0]>'9')
   for(i=1;i<=81;i++){
   m6a:A0[i]=fgetc(file)-48;if(feof(file))exit(8);
      if(A0[i]==-2)A0[i]=0;if(A0[i]<0 || A0[i]>9)goto m6a;}

    sam1=0;
m0s:sam1++;if(sam1>samples){if(argv[3][0]<'9')exit(8);goto m6;}
// printf("%i %i\n",sam1,samples);

m0:for(i=1;i<=81;i++)A[i]=A0[i];part=0;solve();

//now we have a unique-solution sudoku. Now remove clues to make it minimal
part++;
for(i=1;i<=81;i++){mr4:x=(MWC>>8)&127;if(x>=i)goto mr4;x++;P[i]=P[x];P[x]=i;}
for(i1=1;i1<=81;i1++){s1=A[P[i1]];A[P[i1]]=0;if(solve()>1)A[P[i1]]=s1;}

if(rate){nt=0;mi1=9999;for(f=0;f<100;f++){solve();nt+=nodes;if(nodes<mi1)
{mi1=nodes;mi2=C[clues];}}
printf("rating:%6i ,  ",nt);if(rate>1)printf("hint:%s    ",H[mi2]);}
for(i=1;i<=81;i++)printf("%c",L[A[i]]);printf("\n");
goto m0s;}


//-----------------------------------------------------------------------
int solve(){//returns 0 (no solution), 1 (unique sol.), 2 (more than one sol.)
   for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
   clues=0;for(i=1;i<=81;i++)
     if(A[i]){clues++;r=i*9-9+A[i];
       for(j=1;j<=Cols[r];j++){d=Col[r][j];if(Uc[d])return -1;Uc[d]++;
         for(k=1;k<=Rows[d];k++){Ur[Row[d][k]]++;}}}
   for(c=1;c<=m;c++){V[c]=0;for(r=1;r<=Rows[c];r++)if(Ur[Row[c][r]]==0)V[c]++;}

   i=clues;m0=0;m1=0;solutions=0;
m2:i++;I[i]=0;min=n+1;if(i>81 || m0)goto m4;
   if(m1){C[i]=m1;goto m3;}
   w=0;for(c=1;c<=m;c++)if(!Uc[c]) {  if(V[c]<2){C[i]=c;goto m3;}
          if(V[c]<=min){w++;W[w]=c;};
          if(V[c]<min){w=1;W[w]=c;min=V[c];} }
mr:c2=MWC&Two[w];if(c2>=w)goto mr;C[i]=W[c2+1];
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
   r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;m1=0;
   if(part==0){j=9;k=81;x=(r-1)/k+1;y=((r-1)%k)/j+1;s=(r-1)%j+1;A[x*9-9+y]=s;P[x*9-9+y]=i;}
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];
      for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;if(Ur[r1]==1)
         for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]--;
            if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2)m1=c2;}}}
    if(i==81){solutions++;if(solutions>1)return 2;if(part==0)return 1;}
    goto m2;

m4:i--;c=C[i];r=Row[c][I[i]];if(i==clues)goto m9;
   for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]--;
      for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]--;
         if(Ur[r1]==0)for(l=1;l<=Cols[r1];l++){c2=Col[r1][l];V[c2]++;}}}
   if(i>clues)goto m3;
m9:return solutions;}



Last edited by dukuso on Wed Dec 21, 2005 11:23 am; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page 1, 2, 3, 4  Next
Page 1 of 4

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron