#include
using namespace std;
bool canplace(int s[][9],int i,int j,int x,int n) {
for(int k=0;k<n;k++){
if(s[k][j]==x || s[i][k]==x) {
return false;
}
}
int sx=(i/3)*3;
int sy=(j/3)*3;
for(int t=sx;t<sx+3;t++) {
for(int y=sy;y<sy+3;y++) {
if(s[t][y]==x) {
return false;
}
}
}
return true;
}
bool sudoko(int s[][9],int i,int j,int n) {
if(i==n) {
//print s
for(int r=0;r<9;r++) {
for(int y=0;y<9;y++) {
cout<<s[r][y]<<’ ';
}
cout<<endl;
}
return true;
}
if(j==n) {
return sudoko(s,i+1,0,n);
}
if(s[i][j]!=0) {
sudoko(s,i,j+1,n);
}
int x;
for( x=1;x<=n;x++){
if(canplace(s,i,j,x,n)) {
s[i][j]=x;
}
}
if(canplace(s,i,j,x,n)) {
s[i][j]=x;
bool c=sudoko(s,i,j+1,n);
if(c==true) {
return true;
}
s[i][j]=0;
}
return false;
}
int main() {
int s[9][9]={
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
sudoko(s,0,0,9);
}