// I no longer support the method used below.
// see the other thread :
/*
I convinced myself that the best method to write a solver is to
use the dancing links method - but without keeping the whole
4*n*n * n*n*n binary matrix, only the 4 nonzero entries
per row and the 9 nonzero entries per column.
I hope that's possible ?!
And then, always do forced placements immediately.
And check for bifurcations(= 2 possible placements), where
one way leads to a dead end (=contradiction) when filling
in the forced forced placements.
Call such bifurcations "forced placements of level 2".
This should include all the other rules with x-wing, disjoint subset,
etc. They are all forced placements of level 2.
We could extend this to bifurcations, where one way leads
to another bifurcation with two dead ends etc.
I wonder, whether that's what tilps is doing with his
ratings like 1.3.2
*/
// please report improvement suggestions to sterten@aol.com
// solves sudokus, compiled with GCC3.2
/* once you find a forced move and made it, is it better to start new
with examining the first cell or continue as normal ?
to do:
more intelligent input
output solutions only
relable
get "tries" from commandline, default=1
find n=16 or n=9 automatically
testfile:
--7- 4--A G--- --B2
1-G- -7C- --89 ----
-4-5 ---D 7-6E 9---
---- 1--6 -C-5 --3-
-9-- --3- 2-C8 A---
--A- --7- ---- ---B
C-8- ---- -G9- 5-2-
4-2- --AG ---- -C-1
5-9- ---- 82-- -B-D
-G-D -CB- ---- -7-6
2--- ---- -7-- -F--
---6 E9-7 -5-- --8-
-E-- G-1- A--6 ----
---A B8-E C--- F-5-
---- 25-- -E3- -G-9
6C-- ---4 9--F -2--
1 solutions , 109(218) guesses , 21188 placements time=5/91sec.
*/
#include <stdio.h>
#include <time.h>
#define N 66
int n=9,tries=1; //allowed are n=4,n=9 (standard sudoku),n=16,n=25,n=36
char l[65]="-123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#*~";
int m,s,c,a,b,i,j,x,y,q;
int guesses,guess2,try,p=0,max,i1,min1,min,clues,solutions=0,placed;
int A[N][N]; // the array where the sudoku is stored. Blank cells (x,y)
// are represented as A[x][y]=0
int F[N][N][N]; // F for forbidden. F[x][y][s] is set to 1, iff this
// placement would conflict with another placement in the same row,column,block,cell
int C[N][N],By[N],Bx[N];
int X[N*N][N],Y[N*N][N],S[N*N][N],I[N*N],Min[N*N]; // used to store information on bifurcations for later backtracking
int nodes=0,Node[N*N];
FILE *file;
void mark_forbidden_all(int q);
void mark(int q);
int test_rows();
int test_columns();
int test_blocks();
int test_cells();
int test_valid();
int forced_moves();
void print_sudoku();
void read_suduko();
//------------------------------------------------------------------------
int main(int argc,char*argv[]){
clock();
if(argc<2){printf("\nusage:sud9 file with 81-string [max] \n\n");
printf(" prints number of solutions of sudoku-puzzles\n");
printf(" enter empty cells as digit 0, nondigit-characters are ignored\n");
printf(" finds <=max solutions (default max=999), max<0 then shows info\n\n");
exit(1);}
max=999;if(argc>2)sscanf(argv[2],"%i",&max);
if(max<0){max=-max;p=1;}
m=1;while(m*m<n)m++;
for(i=0;i<m;i++)for(j=0;j<m;j++){Bx[i*m+j+1]=1+m*i;By[i*m+j+1]=1+m*j;}
//printf("m=%i ",m);for(i=1;i<=n;i++)printf("%i ",Bx[i]);for(i=1;i<=n;i++)printf("%i ",By[i]);exit(1);
if((file=fopen(argv[1],"rb"))==NULL){fclose(file);printf("file-error\n");exit(1);}
m0:read_suduko(argv[1]);for(x=1;x<=n;x++)for(y=1;y<=n;y++)C[x][y]=A[x][y];
print_sudoku();
if(p>0 && test_valid()==0){printf("not a valid sudoku\n");exit(1);}
if(test_valid()==0)goto m17;
for(try=0;try<tries;try++){ //more than one tries are needed only for benchmarking
for(x=1;x<=n;x++)for(y=1;y<=n;y++)A[x][y]=C[x][y];
mark_forbidden_all(1);
solutions=0;guesses=0;guess2=0;nodes=0;
forced_moves();
if(min==0)goto m17;
mq2:I[clues]=0;
mq1:I[clues]++;if(I[clues]>Min[clues])goto mq8;
i=I[clues];x=X[clues][i];y=Y[clues][i];s=S[clues][i];
// now try all the stored possible placements numbered 1..I[clues]
guess2++;if(i==1)guesses++;
print_sudoku();
if(p)printf(" %i clues , trying move %i : A[%i,%i]=%i\n",clues-1,i,x,y,s);
A[x][y]=s;mark(0);clues++;
if(forced_moves())goto mq2;
if(solutions>=max)goto m17;
mq8:clues--;if(clues<1)goto m17; //take back that placement and backtrack
i=I[clues];x=X[clues][i];y=Y[clues][i];s=S[clues][i];
A[x][y]=0;if(i>=Min[clues])goto mq8;
mark_forbidden_all(0);
if(clues>1)goto mq1;
m17:if(p){printf("\n\n%i solutions , %i(%i) guesses , %i placements ",solutions,guesses,guess2,nodes);if(solutions>=max)printf("or more");
printf(" time=%i/%isec.\n",clock(),CLOCKS_PER_SEC);}
;} // next try
// printf(" time=%i/%isec.\n",clock(),CLOCKS_PER_SEC);
// if(!p)printf("%i\n",solutions);
// if(p==0 && tries>1)printf("%i/%isec.\n",clock(),CLOCKS_PER_SEC);
printf("%i solutions , %i(%i) guesses , %i placements ",solutions,guesses,guess2,nodes);if(solutions>=max)printf("or more");
printf(" time=%i/%isec.\n",clock(),CLOCKS_PER_SEC);
goto m0;
return solutions; }
//------------------------------------------------------------------------
void mark_forbidden_all(int q){
//F[x][y][s] is set to 1 for each cell (x,y) and symbol s
// in conflict with any entry A[x][y]=s , that is :
// s in the same row,column,block, or there is already another symbol in (x,y)
// entry F[x][y][s] is set to 999, iff A[x][y]=s
for(x=1;x<=n;x++)for(y=1;y<=n;y++)for(s=1;s<=n;s++)F[x][y][s]=0;
clues=1;for(x=1;x<=n;x++)for(y=1;y<=n;y++){if(A[x][y]){mark(q);clues++;}}}
//------------------------------------------------------------------------
void mark(int q){
// given x,y,s :
// F[a][b][s] is set to 1 for each cell (a,b) and symbol t
// in conflict with entry A[x][y]=s , that is :
// t=s in the same row,column,block as (x,y) , or other symbol t!=s
// in cell (a,b)=(x,y).
// The entry F[x][y][s] itself is set to 999
// if q=1 is specified, then the entry x,y,s is also stored
int s,i,j;
nodes++;
s=A[x][y];F[x][y][s]=999;
if(q){X[clues][1]=x;Y[clues][1]=y;Min[clues]=1;I[clues]=1;S[clues][1]=s;}
if(s){for(i=1;i<=n;i++){F[i][y][s]|=1;F[x][i][s]|=1;F[x][y][i]|=1;}
for(i=Bx[x];i<Bx[x]+m;i++)for(j=Bx[y];j<Bx[y]+m;j++)F[i][j][s]|=1; } }
//------------------------------------------------------------------------
int test_rows(){
// for row x, symbol s, if there is a unique position in that row where
// symbol s is not forbidden, then put it there store it and update F
for(x=1;x<=n;x++)for(s=1;s<=n;s++){
q=0;for(y=1;y<=n;y++)q+=1-F[x][y][s];if(q>=min1 || q<0)goto m1;
if(q==0){if(p)printf("symbol %c not possible in row %i\n",l[s],x);return 1;}
min=q;min1=q;if(min1==1)min1=2;i1=0;
y=0;m2:y++;if(F[x][y][s])goto m2;
if(q==1){A[x][y]=s;mark(1);placed++;if(p)printf("clue %i : symbol %c into row %i at position %i\n",clues,l[s],x,y);clues++;}
if(q>1){i1++;X[clues][i1]=x;Y[clues][i1]=y;S[clues][i1]=s;if(i1<q)goto m2;}
m1:;} return 0;}
//------------------------------------------------------------------------
int test_columns(){
// for column y, symbol s, if there is a unique position in that column
// where symbol s is not forbidden, then put it there, store it and update F
for(y=n;y>0;y--)for(s=1;s<=n;s++){
q=0;for(x=1;x<=n;x++)q+=1-F[x][y][s];if(q>=min1 || q<0)goto m1;
if(q==0){if(p)printf("symbol %c not possible in column %i\n",l[s],y);return 1;}
min=q;min1=q;if(min1==1)min1=2;i1=0;
x=0;m2:x++;if(F[x][y][s])goto m2;
if(q==1){A[x][y]=s;mark(1);placed++;if(p)printf("clue %i : symbol %c into column %i at position %i\n",clues,l[s],y,x);clues++;}
if(q>1){i1++;X[clues][i1]=x;Y[clues][i1]=y;S[clues][i1]=s;if(i1<q)goto m2;}
m1:;} return 0;}
//------------------------------------------------------------------------
int test_blocks(){
// for block b, symbol s, if there is a unique position in that block where
// symbol s is not forbidden, then put it there, store it and update F
for(b=1;b<=n;b++)for(s=1;s<=n;s++){
q=0;for(i=Bx[b];i<Bx[b]+m;i++)for(j=By[b];j<By[b]+m;j++)
q+=1-F[i][j][s];if(q>=min1 || q<0)goto m1;
if(q==0){if(p)printf("symbol %c not possible in block %i\n",l[s],b);return 1;}
min=q;min1=q;if(min1==1)min1=2;i1=0;
x=Bx[b]-1;m3:x++;y=By[b]-1;m2:y++;if(y>=By[b]+m)goto m3;if(F[x][y][s])goto m2;
if(q==1){A[x][y]=s;mark(1);placed++;if(p)printf("clue %i : symbol %c into block %i at position %i,%i\n",clues,l[s],b,x,y);clues++;}
if(q>1){i1++;X[clues][i1]=x;Y[clues][i1]=y;S[clues][i1]=s;if(i1<q)goto m2;}
m1:;} return 0;}
//------------------------------------------------------------------------
int test_cells(){
// for cell (x,y), if there is a unique symbol which is
// forbidden in this cell, then put it there, store it and update F
for(x=1;x<=n;x++)for(y=1;y<=n;y++){if(A[x][y])goto m1;
q=n;for(s=1;s<=n;s++)q-=F[x][y][s];if(q>=min1)goto m1;
if(q==0){if(p)printf("%i clues , no symbol possible in square %i,%i\n",clues,x,y);return 1;}
min=q;min1=q;if(min1==1)min1=2;i1=0;
s=0;m2:s++;while(F[x][y][s])goto m2;
if(q==1){A[x][y]=s;mark(1);placed++;if(p)printf("clue %i : symbol %c into cell %i,%i\n",clues,l[s],x,y);clues++;}
if(q>1){i1++;X[clues][i1]=x;Y[clues][i1]=y;S[clues][i1]=s;if(i1<q)goto m2;}
m1:;} return 0;}
//------------------------------------------------------------------------
int test_valid(){
// returns 0, iff the sudoku has conflicting entries which forbid a solution
int F[N],x,y,b,s;
for(x=1;x<=n;x++){for(s=1;s<=n;s++)F[s]=0;for(y=1;y<=n;y++){a=A[x][y];if(a*F[a])return 0;F[a]++;}}
for(y=1;y<=n;y++){for(s=1;s<=n;s++)F[s]=0;for(x=1;x<=n;x++){a=A[x][y];if(a*F[a])return 0;F[a]++;}}
for(b=1;b<=n;b++){for(s=1;s<=n;s++)F[s]=0;for(x=Bx[b];x<Bx[b]+m;x++)for(y=By[b];y<By[b]+m;y++){a=A[x][y];if(a*F[a])return 0;F[a]++;}}
return 1;}
//------------------------------------------------------------------------
int forced_moves(){
// find and perform and store all forced moves by the 4 subroutines
// returns the number of placements for a (bi-)furcation after
// no more forced moves can be made
m1:placed=0;min=n*n+9;min1=min;
if(test_columns())return 0;
if(test_blocks())return 0;
if(test_cells())return 0;
if(test_rows())return 0;
if(p)printf("***clues=%i*** min=%i\n",clues,min);
if(placed)goto m1;
Min[clues]=min;
if(p)printf("min=%i\n",min);
if(p && min<n*n)for(i=1;i<=min;i++)printf("i=%i x=%i y=%i s=%i \n",i,X[clues][i],Y[clues][i],S[clues][i]);
if(clues==n*n+1){min=0;Min[n*n+1]=0;solutions++;if(p){printf("solution %i :\n---------------------\n",solutions);print_sudoku();}}
return min; }
//------------------------------------------------------------------------
void print_sudoku(){
int x,y,a;
if(!p)return;
printf("\n\n");
for(x=1;x<=n;x++){for(y=1;y<=n;y++)
{a=A[x][y];printf("%c",l[a]);if(y%m==0)printf(" ");}
printf("\n");if(x%m==0)printf("\n");}printf("\n"); }
//------------------------------------------------------------------------
void read_suduko(){
i=0;for(x=1;x<=n;x++)for(y=1;y<=n;y++){
m6:if(feof(file)){printf("only %i symbols were found\n",i);exit(1);}
a=fgetc(file);if(a=='-' || a=='.'|| a=='0' || a=='*')a=48;
if(a>64 && a<90)a-=7;if(a<48 || a>90)goto m6;
A[x][y]=a-48;
if(A[x][y]<0 || A[x][y]>n)goto m6;
i++;};return;
}
