Sudoku Solver in Turbo C++
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<dos.h>
int p[81][9],b[9][9],a[9][9]/*={
{0,1,6,0,2,0,7,9,0},
{0,0,0,1,0,0,0,0,0},
{5,0,0,7,8,0,0,1,3},
{0,0,0,4,9,0,0,3,0},
{0,5,0,0,0,0,0,6,0},
{0,6,0,0,7,3,0,0,0},
{6,8,0,0,4,1,0,0,5},
{0,0,0,0,0,8,0,0,0},
{0,3,2,0,5,0,1,4,0}}*/,g[9][9]={
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9},
{1,2,3,4,5,6,7,8,9}},p2[81][9];
void fill()
{ int i,j,k,m,n,l[9]={1,2,3,4,5,6,7,8,9};
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(!a[i][j])
{
for(m=0;m<9;m++)
{if(a[i][m])l[a[i][m]-1]=0;
if(a[m][j])l[a[m][j]-1]=0;
}for(n=0;n<9;n++)
if(l[n])a[i][j]=n+1;
}}
}
}
void pos()
{ int i,j,in,k,v,h;
for(i=0;i<81;i++)
for(j=0;j<9;j++)
{
p[i][j]=j+1;
p2[i][j]=j+1;
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(a[i][j])
{
if(j<3&&i<3)
g[0][a[i][j]-1]=0;
else if(i<3&&j<6)
g[1][a[i][j]-1]=0;
else if(i<3&&j<9)
g[2][a[i][j]-1]=0;
else if(j<3&&i<6)
g[3][a[i][j]-1]=0;
else if(i<6&&j<6)
g[4][a[i][j]-1]=0;
else if(i<6&&j<9)
g[5][a[i][j]-1]=0;
else if(j<3&&i<9)
g[6][a[i][j]-1]=0;
else if(i<9&&j<6)
g[7][a[i][j]-1]=0;
else
g[8][a[i][j]-1]=0;
}
}
}
for(i=0;i<9;i++) //test
{
for(j=0;j<9;j++)
{
if(a[i][j])
{
in=i*9;
for(k=0;k<9;k++)
p[in+k][a[i][j]-1]=0;
}
}
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
if(a[i][j])
{
for(k=0;k<9;k++)
p2[j+(k*9)][a[i][j]-1]=0;
}
}
for(i=0;i<81;i++) //p and p2
for(j=0;j<9;j++)
{
if(!p2[i][j])
p[i][j]=0;
}
for(i=0;i<9;i++) //p & g
{ if(i==0)k=0;
else if(i==1)k=3;
else if(i==2)k=9;
else if(i==3)k=27;
else if(i==4)k=30;
else if(i==5)k=33;
else if(i==6)k=54;
else if(i==7)k=57;
else k=60;
for(j=0;j<9;j++)
{
if(!g[i][j])
{
for(v=0;v<19;v+=9)
{
p[k+v][j]=0;
p[k+1+v][j]=0;
p[k+2+v][j]=0;
}
}
}
}
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(a[i][j])
{
h=(i*9)+j;
for(k=0;k<9;k++)
p[h][k]=0;
}
}
void clear(int i,int j)
{
int k,m,n;
for(k=0;k<9;k++)
p[i][k]=0;
m=i%9;
for(k=i-m;k<i-m+9;k++)
p[k][j]=0;
for(k=m;k<81;k+=9)
p[k][j]=0;
if(i<3||(i>8&&i<12)||(i>17&&i<21))
{
for(k=0;k<3;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<6||(i>11&&i<15)||(i>20&&i<24))
{
for(k=3;k<6;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<9||(i>14&&i<18)||(i>23&&i<27))
{
for(k=6;k<9;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<30||(i>35&&i<39)||(i>44&&i<48))
{
for(k=27;k<30;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<33||(i>38&&i<42)||(i>47&&i<51))
{
for(k=30;k<33;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<36||(i>41&&i<45)||(i>50&&i<54))
{
for(k=33;k<36;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<57||(i>62&&i<66)||(i>71&&i<75))
{
for(k=54;k<57;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else if(i<60||(i>65&&i<69)||(i>74&&i<78))
{
for(k=57;k<60;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
else
for(k=60;k<63;k++)
{
p[k][j]=0;
p[k+9][j]=0;
p[k+18][j]=0;
}
}
void check()
{ int i,j,k,t,l,m,n,e,count[9]={0,0,0,0,0,0,0,0,0};
for(i=0;i<9;i++)
{
for(l=0;l<9;l++)count[l]=0;
for(j=i;j<81;j+=9)
{
for(k=0;k<9;k++)
{
if(p[j][k])
count[k]++;
}
}
for(j=0;j<9;j++)
{
if(count[j]==1)
{
for(k=i;k<81;k+=9)
{
if(p[k][j]==j+1)
{
n=k%9;
m=(k-n)/9;
a[m][n]=j+1;
count[j]=0;
clear(k,j);
break;
}
else count[j]=0;
}
}}}
for(i=0;i<81;i+=9) //
{ for(l=0;l<9;l++)count[l]=0;
for(j=i;j<i+9;j++)
{
for(k=0;k<9;k++)
{
if(p[j][k])
count[k]++;
}
}
for(j=0;j<9;j++)
{
if(count[j]==1)
{
for(k=i;k<81;k+=9)
{
if(p[k][j]==j+1)
{
n=k%9;
m=(k-n)/9;
a[m][n]=j+1;
count[j]=0;
clear(k,j);
break;
}
else count[j]=0;
}
}}}
// this is to be checked
for(i=0;i<9;i+=3)
{
for(j=0;j<9;j+=3)
{
for(l=0;l<9;l++)count[l]=0;
t=(i*9)+j;
for(k=t;k<t+3;k++)
{for(l=0;l<9;l++)
{if(p[k][l])++count[l];
if(p[k+9][l])++count[l];
if(p[k+18][l])++count[l];
}
}
for(l=0;l<9;l++)
if(count[l]==1)
{
for(k=t;k<t+3;k++)
{
if(p[k][l])
{
n=k%9;
m=(k-n)/9;
a[m][n]=l+1;
count[l]=0; clear(k,l);
break;
}else
if(p[k+9][l])
{
n=(k+9)%9;
m=(k+9-n)/9;
a[m][n]=l+1; clear(k+9,l);
count[l]=0;
break;
} else
if(p[k+18][l])
{
n=(k+18)%9;
m=(k+18-n)/9;
a[m][n]=l+1; clear(k+18,l);
count[l]=0;
break;
}
else count[k]=0;
}
}}
for(l=0;l<9;l++)count[l]=0;
}
}
void main()
{ clrscr();
int i,j,m=0,k,z,v,c=81,in,h=0,n=0,l;
char ch;
cout<<"Enter Sudoku Grid to Solve (0 for empty space)\n";
for(i=0;i<9;i++)
for(j=0;j<9;j++)
cin>>a[i][j];
pos();
for(i=0;i<9;i++)
for(j=0;j<9;j++)b[i][j]=a[i][j];
do
{
check();
clrscr();
c=81;
cout<<"\n\nGiven Sudoku Grid \t\t Solved Sudoku\n\n";
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
if(b[i][j])cout<<b[i][j]<<" ";
else cout<<" ";
cout<<"\t\t";
for(j=0;j<9;j++)
if(a[i][j])
{
cout<<a[i][j]<<" ";
--c;
}
else cout<<" ";
cout<<"\n";
} if(kbhit())ch=getch();
if(ch=='e')break;
if(l==c)fill();
l=c;
}while(c);
getch();
}
No comments:
Post a Comment