C Program to solve a 9*9 Sudoku


Here is a program that I wrote to solve Sudoku sometime back. Posting on the blog now.

#include

int show_sudoku();

static int sudoku_nos[9][9]= {
{3,0,5,4,0,1,6,0,2},
{0,0,0,0,0,0,0,5,1},
{6,0,0,0,0,9,7,0,0},
{0,0,0,0,0,0,0,0,4},
{0,0,0,6,4,5,0,0,9},
{4,3,7,0,0,8,2,0,5},
{0,0,0,0,6,2,0,0,0},
{0,5,4,0,1,0,0,8,6},
{8,7,0,0,5,0,1,2,0}
};

static short int vals_g[]={1,2,3,4,5,6,7,8,9};
static short int others_options[]={1,2,3,4,5,6,7,8,9};

int show_possiblities(int i, int j,short int vals[])
{
int m=0,n=0,count=9,udi=0;
for(m=0;m<9;m++)
{
if(sudoku_nos[i][m]!=0)
{
vals[sudoku_nos[i][m]-1]=0;
count--;
}
}
for(m=0;m<9;m++)
{
if((sudoku_nos[m][j]!=0)&& vals[sudoku_nos[m][j]-1]!=0)
{
vals[sudoku_nos[m][j]-1]=0;
count--;
}
}
for(m=(i-(i%3));m<((i-(i%3))+3);m++)
{
   for(n=(j-(j%3));n<((j-(j%3))+3);n++)
{
if((sudoku_nos[m][n]!=0)&& vals[sudoku_nos[m][n]-1]!=0)
{
vals[sudoku_nos[m][n]-1]=0;
count--;
}
}
}
return count;
}

void check_others_options(int i, int j,short int vals_o[])
{
int m=0,n=0,count;
for(m=(i-(i%3));m<((i-(i%3))+3);m++)
{
  for(n=(j-(j%3));n<((j-(j%3))+3);n++)
{
if(i!=m&&j!=n&&sudoku_nos[m][n]==0)
{
count=show_possiblities(m,n,vals_o);
if((sudoku_nos[m][n]!=0)&& vals_o[sudoku_nos[m][n]-1]!=0)
{
vals_o[sudoku_nos[m][n]-1]=0;
}
}
}
}
}

void solve_sudoku()
{
int i,j,count,count_o,m,k=0,r=0,udi=0,x=0,y=0,xx,yy,dd,d,z;

    while(true)
{
k=0;
for(i=0;i<9;i++)
{
printf("\n");
for(j=0;j<9;j++)
{
if(sudoku_nos[i][j]==0)
{
k=1;
for(m=0;m<9;m++)
{
vals_g[m] = m+1;
others_options[m]=m+1;
}
count=show_possiblities(i,j,vals_g);
check_others_options(i,j,others_options);
if(count==1)
{
udi=0;
r=0;
    printf("\n%d,%d=",i+1,j+1);
    for(m=0;m<9;m++)
{
if(vals_g[m]!=0)
{
printf("%d",vals_g[m]);
sudoku_nos[i][j]=vals_g[m];
show_sudoku();
printf("\n");
}
}
}
else if(r>80&&count<3)
{ x=0;y=0,d=0;
for(m=0;m<9;m++)
{
if(vals_g[m]!=0)
{
if(x!=0)x=vals_g[m];
else
if(y!=0)y=vals_g[m];
else
d=vals_g[m];
}
}
xx=0;yy=0;//dd=0;
for(z=0;z<9;z++)
{
if(x==others_options[z]) xx=10;
if(y==others_options[z]) yy=10;
//if(d==others_options[z]) dd=10;
}
if(yy!=10 && (xx==10 && dd==10)){ sudoku_nos[i][j]=yy; udi=0; r=0; printf("\n%d,%d=%d",i+1,j+1,yy);}
if(xx!=10 && (yy==10 && dd==10)){ sudoku_nos[i][j]=xx; udi=0; r=0; printf("\n%d,%d=%d",i+1,j+1,xx);}
//if(dd!=10 && (yy==10 && xx==10)){ sudoku_nos[i][j]=dd; udi=0; r=0; printf("\n%d,%d=%d",i+1,j+1,dd);}
if(r!=0){
show_sudoku();
printf("\n%d options for %d,%d:",count,i,j);
for(m=0;m<9;m++)
{
if(vals_g[m]!=0)
printf("%d ",vals_g[m]);
}
printf("\nUdi mara: ");
scanf("%d",&udi);
if(udi<9&&udi>0)sudoku_nos[i][j]=udi;
udi=0; r=0;
}
}
}
}
}
if(k==0) break;
r++;
}
}


int show_sudoku()
{
int i=0,j=0;
for(i=0;i<9;i++)
{
printf("\n");
for(j=0;j<9;j++)
{
if(sudoku_nos[i][j]<=0||sudoku_nos[i][j]>9)
printf(" * ");
else
printf(" %d ", sudoku_nos[i][j]);
}
}
return 0;
}

int main()
{
//check & solve
    solve_sudoku();
    //Print the input
show_sudoku();
printf("\n");
getchar();
return 0;
}

Comments

Popular posts from this blog

Saturday, 30th December 2023

Monday, Nov 20, 2023

Time, Timing & Making Things Happen