#include
#include<math.h>
using namespace std;
bool canPlace(int Suduko[][9],int x,int y,int number,int n){
//For rows
for(int i=0;i<9;i++){
if(Suduko[i][y] == number){
return false;
}
}
//For column
for(int i=0;i<9;i++){
if(Suduko[x][i] == number){
return false;
}
}
//For subgrid
int sroot = sqrt(n);
int a = (x/sroot)*sroot;
int b = (y/sroot)*sroot;
for(int i=a;i<(a+sroot);i++){
for(int j=b;j<(b+sroot);j++){
if(Suduko[i][j] == number){
return false;
}
}
}
return true;
}
bool solveSudoKo(int Sudoko[][9],int row,int column,int n){
//All rows completed
if(row == n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<Sudoko[i][j]<<" ";
}
cout<<endl;
}
return true;
}
//Prefilled cells
if(Sudoko[row][column] != 0){
return solveSudoKo(Sudoko,row,column+1,n);
}
//Completion of one row
if(column == n){
return solveSudoKo(Sudoko,row+1,0,n);
}
for(int number=1;number<=n;number++){
if(canPlace(Sudoko,row,column,number,n)){
Sudoko[row][column] = number;
bool b = solveSudoKo(Sudoko,row,column+1,n);
if(b == true){
return true;
}
}
}
Sudoko[row][column] = 0;
return false;
}
int main(){
int Sudoko[9][9] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
solveSudoKo(Sudoko,0,0,9);
return 0;
}