Sudoku Solver using C/C++

Hey guys, today I am posting the code of one of my favorite project which I did when I was in first year of engineering. Hope you guys like it.





Here's the code, enjoy coding.

/*
Project: Sudoku Solver using C/C++
Programmer: Ashok Kumar Shrestha
*/
#include<graphics.h>
#include<conio.h>
#include<dos.h>
#include<process.h>
#include<iostream.h>
#include<stdio.h>
int mat1[9][9];  //for printing given problem

//////////////////graphics initialization///////////////////////////
union REGS i, o;
struct SREGS s;
int initmouse()
{
   i.x.ax = 0;
   int86(0X33,&i,&o);
   return ( o.x.ax );
}

void showmouseptr()
{
   i.x.ax = 1;
   int86(0X33,&i,&o);
}

void getmousepos(int *button, int *x, int *y)
{
   i.x.ax = 3;
   int86(0X33,&i,&o);

   *button = o.x.bx;
   *x = o.x.cx;
   *y = o.x.dx;
}
void hidemouseptr()
{
i.x.ax=2;
int86(0x33,&i,&o);
}
restrictmouseptr(int x1,int y1,int x2,int y2)
{
i.x.ax=7;
i.x.cx=x1;
i.x.dx=x2;
int86(0x33,&i,&o);
i.x.ax=8;
i.x.cx=y1;
i.x.dx=y2;
int86(0x33,&i,&o);
return 0;
}

//////////////////subroutines////////////////////////////////////////
void display(int mat[10][9][9]);
void add_num(int mat[10][9][9],int x,int y);
void process_data(int dat_mat[10][9][9]);
void pair_checked1(int dat_mat[10][9][9]);
void get_mat();
void grid();
int check_num(int mat[10][9][9]);

int mat[9][9]={{0,0,0,0,0,0,2,0,9}, //pro
      {0,0,0,0,2,0,0,3,0},
      {8,4,0,0,0,1,0,0,0},
      {2,0,0,0,0,9,0,8,6},
      {0,0,5,8,0,0,0,0,0},
      {6,0,0,0,0,7,9,4,0},
      {0,0,0,0,0,0,6,0,8},
      {0,2,0,0,0,0,0,7,0},
      {1,0,0,0,3,5,0,0,0}};

int check_num(int mat[10][9][9])  ////check if wrong no is placed
{
int i,j;
for(i=0;i<9;i++)
{
int ck_num[9]={0};
for(j=0;j<9;j++)
{ if(mat[0][i][j])
{
ck_num[mat[0][i][j]-1]++;
if(ck_num[mat[0][i][j]-1]>1)
{ return 0;}
}
}
}

for(i=0;i<9;i++)
{
int ck_num[9]={0};
for(j=0;j<9;j++)
{ if(mat[0][j][i])
{
ck_num[mat[0][j][i]-1]++;
if(ck_num[mat[0][j][i]-1]>1)
{ return 0;}
}
}
}

for(i=0;i<9;i++)
{
int ck_num[9]={0};
int x1=(i/3)*3,y1=(i%3)*3,x,y;
for(x=x1;x<x1+3;x++)
{
  for(y=y1;y<y1+3;y++)
  {
if(mat[0][x][y])
{
ck_num[mat[0][x][y]-1]++;
if(ck_num[mat[0][x][y]-1]>1)
{ return 0;}
}
  }
}
}
return 1;
}
void find(int mat[10][9][9]) ////find if we got solution
{
int i,j,k=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{ if(mat[0][i][j]) k++; }
if(check_num(mat)&&k==81)
{ cleardevice();
grid();
get_mat();
}
}


int c1(int mat[10][9][9])      ////count no. in dat_mat[0][i][j]
{
int i,j,co=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{     if(mat[0][i][j]) co++;   }
if(co==81) return 1;
return 0;
}

void guess1(int dat_mat[10][9][9])   //guess the remaining number.
{
if(!check_num(dat_mat))
return;

int i,j,k,x,y,x1,y1;
int dat[10][9][9]={0};
for(i=0;i<10;i++)
for(j=0;j<9;j++)
for(k=0;k<9;k++)
dat[i][j][k]=dat_mat[i][j][k];

for(i=1;i<10;i++)
{
for(j=0;j<9;j++)
{
x1=(j/3)*3; y1=(j%3)*3;
int count=0,ges[9]={0};
for(x=x1;x<x1+3;x++)
for(y=y1;y<y1+3;y++)
if(!dat_mat[i][x][y])
{ ges[count++]=x*10+y;}
if(count==2)
{
for(k=0;k<count;k++)
{     dat_mat[i][ges[k]/10][ges[k]%10]=1;
dat_mat[0][ges[k]/10][ges[k]%10]=i;
process_data(dat_mat);
find(dat_mat);
for(int z=0;z<9;z++)
pair_checked1(dat_mat);
process_data(dat_mat);
find(dat_mat);
pair_checked1(dat_mat);
process_data(dat_mat);
find(dat_mat);
if(!c1(dat_mat))
{ guess1(dat_mat);
}
else
{
dat[i][ges[k]/10][ges[k]%10]=0;
}
for(int i1=0;i1<10;i1++)
for(int j1=0;j1<9;j1++)
{
   for(int k1=0;k1<9;k1++)
dat_mat[i1][j1][k1]=dat[i1][j1][k1];
}
   }
}

}
}
}


void pair_checked1(int dat_mat[10][9][9])
{
//ckecking for pairs

int i,j,k,adx,ady,p,nums,count,n,cnt;

  for(i=0;i<9;i++)
  {
  {
   cnt=0;
   int x1=(i/3)*3, y1=(i%3)*3;
//finding remaining elements in box
int rbox[9]={0};
for(int x=x1;x<x1+3;x++)
for(int y=y1;y<y1+3;y++)
if(dat_mat[0][x][y])
{       int val=dat_mat[0][x][y]  ;
rbox[val-1]=val; //elements present in box are filled with 2
}
//assining remaininig element of box to grp[1][]
int grp[3][9]={0},count=0;
for(j=0;j<9;j++)
if(!rbox[j])
{ grp[1][cnt++]=j+1;    }
   for(j=0;j<cnt-1;j++)
   {
    if(!grp[2][j])
    {
     nums=1;
     for(k=j+1;k<cnt;k++)
     {
       count=0;
       n=0;
       if(!grp[2][k])
       {
       for(n=0;n<9;n++)
       {
adx=i/3*3+(n/3);
ady=i%3*3+(n%3);
if(dat_mat[grp[1][j]][adx][ady]!=dat_mat[grp[1][k]][adx][ady])
break;
if(!dat_mat[grp[1][j]][adx][ady])
{
grp[0][count]=adx*10+ady;
count++;
}
       }
       if(n>8)
       {
grp[2][k]=j+1;
nums++;
if(nums==count)
{
grp[2][j]=j+1;
for(p=0;p<cnt;p++)
{
 if(grp[2][p]-j-1)
   for(n=0;n<count;n++)
dat_mat[grp[1][p]][grp[0][n]/10][grp[0][n]%10]=1;

}
}
       }
      }
     }
     grp[2][j]=j+1;
    }
   }
  }
 }
 process_data(dat_mat);
 find(dat_mat);
}

void solve()
{
int dat_mat[10][9][9]={0};
int x,y,i,j,k,l,val,c2=0,c1=0;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{ if(mat[i][j])
{ mat1[i][j]=mat[i][j];
c2++;
}
}
}
//this initializes 3d mat ie. 0 floor contains mat value n remaining floor pos where val can be.
for(x=0;x<9;x++)
{
for(y=0;y<9;y++)
{
if(mat[x][y])
{
val=mat[x][y];
dat_mat[0][x][y]=val;//dat_mat[0][x][y] represents at 0 floor at x,y postion value is stored.
for(k=0;k<9;k++)//this is to initialize all top floor(1 to 9),row n col of particular val(floor) to not possible.
{
dat_mat[k+1][x][y]=1; //here 1 represents that position can not be filled with any number.
dat_mat[val][x][k]=1;//col to np
dat_mat[val][k][y]=1;//row to np
}
int i1=(x/3)*3, j1=(y/3)*3;
for(i=i1;i<i1+3;i++)
for(j=j1;j<j1+3;j++)
{ dat_mat[val][i][j]=1;}//box to np
dat_mat[val][x][y]=2;//in this position one value is filled.
}
}
}

do                   //loop to continues if process is generating new no.
{       c1=c2;
c2=0;
process_data(dat_mat);   //calls to process data.
for(i=0;i<9;i++)
pair_checked1(dat_mat);
process_data(dat_mat);
find(dat_mat);
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{ if(mat[i][j]) c2++; }


}while(c1<c2);
guess1(dat_mat);
display(dat_mat);
}

//add the number to 3d array after calculation at pos x,y
void add_num(int dat_mat[10][9][9],int x,int y)
{
if(mat[x][y])
{
int val=mat[x][y];

for(int k=0;k<9;k++)//this is to initialize all top floor(1 to 9),row n col of particular val(floor) to not possible.
{
dat_mat[k+1][x][y]=1; //here 1 represents that position can not be filled with any number.
dat_mat[val][x][k]=1;//col to np
dat_mat[val][k][y]=1;//row to np
}
int i1=(x/3)*3, j1=(y/3)*3;
for(int i=i1;i<i1+3;i++)
for(int j=j1;j<j1+3;j++)
{ dat_mat[val][i][j]=1;}//box to np
dat_mat[0][x][y]=val;//dat_mat[0][x][y] represents at 0 floor at x,y postion value is stored.
dat_mat[val][x][y]=2;//in this position one value is filled.
}
}
//display content of 3d array
void display(int dat_mat[10][9][9])
{
int i,j,k;
for(i=0;i<10;i++)
{
clrscr();
int cnt=0;
cout<<"floor no. :  "<<i<<"\n\n";
for(j=0;j<9;j++)
{       if(j%3==0) cout<<"\n";
for(k=0;k<9;k++)
{       if(k%3==0) cout<<"   ";
cout<<"   "<<dat_mat[i][j][k];
if(dat_mat[i][j][k]) cnt++;
}
cout<<"\n\n";
}
cout<<cnt;
      if(getch()=='d') exit(0);
}
}
void process_data(int dat_mat[10][9][9])
{
int i,j,x,y;
//process the data, checks for single pos in row,col n box.

int numc,numr;
for(i=1;i<10;i++)
{
for(x=0;x<9;x++)
{
int countc=0;//countr=0;
for(y=0;y<9;y++)
{
if(!dat_mat[i][x][y])//checks single col
{
countc++;
numc=y;
}
}
if(countc==1)
{
mat[x][numc]=i;
add_num(dat_mat,x,numc);
}

}
}

//checks single box

for(i=1;i<10;i++)
{
for(j=0;j<9;j++)
{

int countb=0,numb;
int x1=(j/3)*3, y1=(j%3)*3;
for(x=x1;x<x1+3;x++)
{
for(y=y1;y<y1+3;y++)
{
if(dat_mat[i][x][y]==2||countb>1)
break;
if(!dat_mat[i][x][y])
{
countb++;
numb=x*10+y;
}

}
}
if(countb==1)
{
mat[numb/10][numb%10]=i;
add_num(dat_mat,numb/10,numb%10);
}

}
}
}
int getkey()
{
union REGS i,o;
while(!kbhit())
;
i.h.ah=0;
int86(22,&i,&o);
return(o.h.ah);
}

void grid()
{
int cl=9,cg=15,i,j;//cl-line color,cg-background color
cleardevice();
int cx,cy,box_siz=40;

cx=getmaxx()/2;
cy=getmaxy()/2;
int x1,y1;
y1=cy-(9*box_siz)/2;
x1=cx-(9*box_siz)/2;

setfillstyle(1,cl);//outermost rect.
bar(x1-5,y1-40,x1+9*box_siz+5,y1+9*box_siz+50);

setfillstyle(1,cg);//square
bar(x1,y1,x1+9*box_siz,y1+9*box_siz);

setfillstyle(1,3);//option box
bar(x1,y1+9*box_siz+15,x1+9*box_siz,y1+9*box_siz+45);

setcolor(10);  //option box highlighter
line(x1,y1+9*box_siz+15,x1+9*box_siz,y1+9*box_siz+15);
line(x1,y1+9*box_siz+15,x1,y1+9*box_siz+45);
line(x1+3*box_siz+6,y1+9*box_siz+15,x1+3*box_siz+6,y1+9*box_siz+45);
line(x1+6*box_siz+6,y1+9*box_siz+15,x1+6*box_siz+6,y1+9*box_siz+45);

setfillstyle(1,cl);//separates boxes
bar(x1+3*box_siz,y1,x1+3*box_siz+5,y1+9*box_siz+50);
bar(x1+6*box_siz,y1,x1+6*box_siz+5,y1+9*box_siz+50);
bar(x1,y1+3*box_siz,x1+9*box_siz,y1+3*box_siz+5);
bar(x1,y1+6*box_siz,x1+9*box_siz,y1+6*box_siz+5);

setcolor(cl);
for(i=1;i<9;i++)
{
line(x1+i*40,y1,x1+i*40,y1+9*box_siz);
line(x1,y1+i*40,x1+9*box_siz,y1+i*40);
}
setcolor(0);
line(x1-5,y1+9*box_siz+8,x1+9*box_siz+5,y1+9*box_siz+8);

setcolor(14);
settextstyle(4,0,4);
outtextxy(x1+15,y1-40,"S U D O K U  Solver");

setcolor(14);
settextstyle(2,0,8);
outtextxy(x1+20,y1+9*box_siz+15,"Solve");
outtextxy(x1+160,y1+9*box_siz+15,"New");
outtextxy(x1+280,y1+9*box_siz+15,"Quit");

for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{       if(mat[j][i])
{
int x2=x1+i*box_siz+15;
int y2=y1+j*box_siz ;
char array[40];
if(!mat1[j][i])
setcolor(2);
else
setcolor(1);
settextstyle(3,0,4);
hidemouseptr();
moveto(x2,y2);

sprintf(array,"%d",mat[j][i]);
outtext(array);
showmouseptr();
}
}
}
}
void main()
{
int gd = DETECT, gm;
initgraph(&gd,&gm,"..\\BGI");
get_mat();
}
void get_mat()   //gets value of mat[9][9] through mouse n keyboard
{
int  button=-1, x=0, y=0;
int box_siz=40;
char array[40];
settextstyle(GOTHIC_FONT,0,2);
int i,j,k,l;
grid();
int cx,cy;

cx=getmaxx()/2;
cy=getmaxy()/2;
int x1,y1;
y1=cy-(9*box_siz)/2;
x1=cx-(9*box_siz)/2;
while(1)
{
restrictmouseptr(136,60,500,460);
showmouseptr();
getmousepos(&button,&x,&y);
gotoxy(1,10);
printf("x%3d, y%3d",x,y);
int row,col,opt_box;
if(button==1)
{
if(y<(y1+9*box_siz))
{
col=(x-x1)/box_siz;
row=(y-y1)/box_siz;
setcolor(1);
settextstyle(3,0,4);
int x2=x1+col*box_siz+15;
int y2=y1+row*box_siz ;
gotoxy(1,15);
printf("r%3d, c%3d",row,col);
int val=getkey()-1;
hidemouseptr();
if(mat[row][col])
{
setfillstyle(1,15);
bar(x1+col*box_siz+5,y1+row*box_siz+5,x1+(col+1)*box_siz-5,y1+(row+1)*box_siz-5);
}

if(val&&val<10)
{ mat[row][col]=val;
moveto(x2,y2);
sprintf(array,"%d",val);
outtext(array);
}
showmouseptr();
}
else
{
opt_box=(x-x1)/(3*box_siz)+1;
gotoxy(1,20);
printf("box=%2d",opt_box);
switch(opt_box)
{
case 1:
gotoxy(1,1);
for(i=0;i<9;i++)
{ for(j=0;j<9;j++)
{ printf("%d",mat[i][j]); }
printf("\n");
}
solve();

break;
case 2:
for(i=0;i<9;i++)
{ for(j=0;j<9;j++)
{ mat[i][j]=0;
mat1[i][j]=0;
}
}
grid();
break;
case 3:
delay(126);
exit(0);
}
}
button=-1;
}
else if(button==2)
{
button=-1;
delay(200);
exit(1);
}
else
button=-1;
}
}




























Comments

Post a Comment

Popular posts from this blog

Wizard Quiz: Privacy Policy

Wizard Quiz: Privacy Policy Ashok Kumar Shrstha built the Wizard Quiz app as an Ad Supported app. This SERVICE is provided by Ashok Kumar Shrstha at no cost and is intended for use as is.  This page is used to inform visitors regarding my policies with the collection, use, and disclosure of Personal Information if anyone decided to use my Service. If you choose to use my Service, then you agree to the collection and use of information in relation to this policy. The Personal Information that I collect is used for providing and improving the Service. I will not use or share your information with anyone except as described in this Privacy Policy. The terms used in this Privacy Policy have the same meanings as in our Terms and Conditions, which is accessible at Wizard Quiz unless otherwise defined in this Privacy Policy.
Read more

Sorting Hat: Privacy Policy

Privacy Policy Ashok Kumar Shrestha built the Sorting Hat app as an Ad Supported app. This SERVICE is provided by Ashok Kumar Shrestha at no cost and is intended for use as is. This page is used to inform visitors regarding my policies with the collection, use, and disclosure of Personal Information if anyone decided to use my Service. If you choose to use my Service, then you agree to the collection and use of information in relation to this policy. The Personal Information that I collect is used for providing and improving the Service. I will not use or share your information with anyone except as described in this Privacy Policy. The terms used in this Privacy Policy have the same meanings as in our Terms and Conditions, which is accessible at Sorting Hat unless otherwise defined in this Privacy Policy.
Read more

mTranslator

Image
"mTranslater" is an android application developed for educational purpose and is free of cost. It is intended to be used by foreign tourist for some basic conversation. This app will be handy during your visit in Nepal and India. The sentences used in this app are meant for communication purpose only and may or may not be grammatically correct. In this app, commonly spoken sentences are translated into Nepali, Hindi and Kannada and are presented in both native language font and English font. Additional buttons are provided to control/play translated queries. You can find the application for free in play-store . Enjoy the app.
Read more