Successfully coded an easy to understand SU-DO-KU solver for C++...........
The code is as follows ..............
//*** SU-DO-KU solver *** !! *** authored @ hYDRO ***\\
#include<iostream.h>
#include<conio.h>
void main()
{ clrscr();
int k[9][9],K[9][9],i,j,i1,j1,i2,j2,error,temp,count=0;
cout<<"Enter SUDOKU problem (0 for blanks) : "<<endl;
for(i=0;i<9;i++)
{ for(j=0;j<9;j++)
{ cin>>K[i][j]; //!!! MATRIX INPUT !!!
k[i][j]=K[i][j];
} }
cout<<"O.K.? (Enter 0 if OK, 1 to update): ";
cin>>error;
if(error==0)
goto matrixvalidation;
matrixupdation:
while(1)
{
cout<<"Enter Row, Col, Revised number:(0 to exit) ";
cin>>i>>j>>temp; //!!! CORRECTION !!!
if(i>0&&j>0&&temp>=0&&i<10&&j<10&&temp<10)
{
K[i-1][j-1]=temp;
k[i-1][j-1]=temp;
}
else
cout<<"Enter row/column/no. invalid.";
}
matrixvalidation:
cout<<"Input matrix: "<<endl;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++) //!!! CONFIRMATION OF MATRIX!!!
cout<<k[i][j]<<" ";
cout<<endl;
}
for(i=0;i<9;i++) //!!! CHECKING VALIDITY !!!
for(j=0;j<9;j++)
if(k[i][j]<0||k[i][j]>9)
{
cout<<endl<<i+1<<" "<<j+1<<" "<<k[i][j]
<<" Number isn't b/w 1 and 9.";
goto matrixupdation;
}
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
if(k[i][j]==0)
continue;
error=0;
for(i1=0;i1<9;i1++)
if(i!=i1&&k[i][j]==k[i1][j])
{
error=1;
i2=i1;
j2=j;
}
for(j1=0;j1<9;j1++)
if(j!=j1&&k[i][j]==k[i][j1])
{
error=1;
i2=i;
j2=j1;
}
for(i1=0;i1<9;i1++)
for(j1=0;j1<9;j1++)
if((i!=i1||j!=j1)&&i/3==i1/3&&j/3==j1/3&&k[i][j]==k[i1][j1])
{
error=1;
i2=i1;
j2=j1;
}
if(error)
{
cout<<endl<<i+1<<","<<j+1<<" and "<<i2+1<<","<<j2+1
<<" have same value.";
goto matrixupdation; //!!! VALIDATION CHECK COMPLETED !!!
}
}
for(i=0;i<9;i++) //!!! LOGIC STARTS !!!
for(j=0;j<9;j++)
{
if(K[i][j]>0)
goto chksol;
for(k[i][j]++;k[i][j]<=9;k[i][j]++)
{
error=0;
for(i1=0;i1<9;i1++) //!!! ROW CHECKING !!!
if(i!=i1&&k[i][j]==k[i1][j])
error=1;
for(j1=0;j1<9;j1++) ///!!! COLOUMN CHECKING !!!
if(j!=j1&&k[i][j]==k[i][j1])
error=1;
for(i1=0;i1<9;i1++) //!!! 3*3 BLOCK CHECKING !!!
for(j1=0;j1<9;j1++)
if((i!=i1||j!=j1)&&i/3==i1/3&&j/3==j1/3&&k[i][j]==k[i1][j1])
error=1;
if(error==0)break;
}
if(k[i][j]>9) //!!! RESTARTING CYCLE !!!
{
k[i][j]=0;
do
{
if(i==0&&j==0)goto nomoresol;
if(j>0)
j--;
else
{ j=8;
i--; }
}while(K[i][j]>0);
j--;
}
chksol: if(i==8&&j==8)
{
cout<<"Solution: "<<++count<<endl;
for(i1=0;i1<9;i1++) //!!! SOLUTION OUTPUT !!!
{
for(j1=0;j1<9;j1++)
cout<<k[i1][j1]<<" ";
cout<<endl;
}
if(count==50) //!!! WON'T SOLVE IF MORE THAN 50 SOLN !!!
{
cout<<"Too many solutions. Not checking for more solutions.";
return;
}
while(K[i][j]>0)
{
if(i==0&&j==0) //!!! NEXT SOLN !!!
goto nomoresol;
if(j>0)
j--;
else
{ j=8;
i--; }
}
k[i][j]=0;
do
{
if(i==0&&j==0)goto nomoresol;
if(j>0)
j--;
else
{ j=8;
i--; }
}while(K[i][j]>0);
j--;
} }
nomoresol:
if(count>0) //!!! IF SOLN LESS THAN 50 !!!
cout<<"No more solutions.";
else //!!! IF 50 SOLN REACHED !!!
cout<<"No solution.";
getch();
}
The code is as follows ..............
//*** SU-DO-KU solver *** !! *** authored @ hYDRO ***\\
#include<iostream.h>
#include<conio.h>
void main()
{ clrscr();
int k[9][9],K[9][9],i,j,i1,j1,i2,j2,error,temp,count=0;
cout<<"Enter SUDOKU problem (0 for blanks) : "<<endl;
for(i=0;i<9;i++)
{ for(j=0;j<9;j++)
{ cin>>K[i][j]; //!!! MATRIX INPUT !!!
k[i][j]=K[i][j];
} }
cout<<"O.K.? (Enter 0 if OK, 1 to update): ";
cin>>error;
if(error==0)
goto matrixvalidation;
matrixupdation:
while(1)
{
cout<<"Enter Row, Col, Revised number:(0 to exit) ";
cin>>i>>j>>temp; //!!! CORRECTION !!!
if(i>0&&j>0&&temp>=0&&i<10&&j<10&&temp<10)
{
K[i-1][j-1]=temp;
k[i-1][j-1]=temp;
}
else
cout<<"Enter row/column/no. invalid.";
}
matrixvalidation:
cout<<"Input matrix: "<<endl;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++) //!!! CONFIRMATION OF MATRIX!!!
cout<<k[i][j]<<" ";
cout<<endl;
}
for(i=0;i<9;i++) //!!! CHECKING VALIDITY !!!
for(j=0;j<9;j++)
if(k[i][j]<0||k[i][j]>9)
{
cout<<endl<<i+1<<" "<<j+1<<" "<<k[i][j]
<<" Number isn't b/w 1 and 9.";
goto matrixupdation;
}
for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
if(k[i][j]==0)
continue;
error=0;
for(i1=0;i1<9;i1++)
if(i!=i1&&k[i][j]==k[i1][j])
{
error=1;
i2=i1;
j2=j;
}
for(j1=0;j1<9;j1++)
if(j!=j1&&k[i][j]==k[i][j1])
{
error=1;
i2=i;
j2=j1;
}
for(i1=0;i1<9;i1++)
for(j1=0;j1<9;j1++)
if((i!=i1||j!=j1)&&i/3==i1/3&&j/3==j1/3&&k[i][j]==k[i1][j1])
{
error=1;
i2=i1;
j2=j1;
}
if(error)
{
cout<<endl<<i+1<<","<<j+1<<" and "<<i2+1<<","<<j2+1
<<" have same value.";
goto matrixupdation; //!!! VALIDATION CHECK COMPLETED !!!
}
}
for(i=0;i<9;i++) //!!! LOGIC STARTS !!!
for(j=0;j<9;j++)
{
if(K[i][j]>0)
goto chksol;
for(k[i][j]++;k[i][j]<=9;k[i][j]++)
{
error=0;
for(i1=0;i1<9;i1++) //!!! ROW CHECKING !!!
if(i!=i1&&k[i][j]==k[i1][j])
error=1;
for(j1=0;j1<9;j1++) ///!!! COLOUMN CHECKING !!!
if(j!=j1&&k[i][j]==k[i][j1])
error=1;
for(i1=0;i1<9;i1++) //!!! 3*3 BLOCK CHECKING !!!
for(j1=0;j1<9;j1++)
if((i!=i1||j!=j1)&&i/3==i1/3&&j/3==j1/3&&k[i][j]==k[i1][j1])
error=1;
if(error==0)break;
}
if(k[i][j]>9) //!!! RESTARTING CYCLE !!!
{
k[i][j]=0;
do
{
if(i==0&&j==0)goto nomoresol;
if(j>0)
j--;
else
{ j=8;
i--; }
}while(K[i][j]>0);
j--;
}
chksol: if(i==8&&j==8)
{
cout<<"Solution: "<<++count<<endl;
for(i1=0;i1<9;i1++) //!!! SOLUTION OUTPUT !!!
{
for(j1=0;j1<9;j1++)
cout<<k[i1][j1]<<" ";
cout<<endl;
}
if(count==50) //!!! WON'T SOLVE IF MORE THAN 50 SOLN !!!
{
cout<<"Too many solutions. Not checking for more solutions.";
return;
}
while(K[i][j]>0)
{
if(i==0&&j==0) //!!! NEXT SOLN !!!
goto nomoresol;
if(j>0)
j--;
else
{ j=8;
i--; }
}
k[i][j]=0;
do
{
if(i==0&&j==0)goto nomoresol;
if(j>0)
j--;
else
{ j=8;
i--; }
}while(K[i][j]>0);
j--;
} }
nomoresol:
if(count>0) //!!! IF SOLN LESS THAN 50 !!!
cout<<"No more solutions.";
else //!!! IF 50 SOLN REACHED !!!
cout<<"No solution.";
getch();
}
Comments
Post a Comment