//CODE 29: N-queen problem
#include
#include<math.h>
using namespace std;
bool checkNumberPlacement(int sudoku[][9], int i, int j, int n, int number)
{
//check if it is present in the complete row or column
for(int a=0; a<n; a++)
{
if(sudoku[i][a]==number||sudoku[a][j]==number)
{return false;}
}
//check inside the smaller block get the starting row/column for the block
int sub_array_size = sqrt(n);
int sx = (i/sub_array_size)*sub_array_size;
int sy = (j/sub_array_size)*sub_array_size;
for(int a=sx; a<sx+sub_array_size; a++)
{
for(int b=sy; b<sy+sub_array_size; b++)
{
if(sudoku[a][b]==number)
{
return false;
}
}
}
return true;
}
bool sudokuSolver(int sudoku[][9], int i, int j, int n)
{
if(i==n)
{
//print matrix
for(int a=0; a<n; a++)
{
for(int b=0; b<n; b++)
{
cout<<sudoku[a][b]<<" ";
}
cout<<endl;
}
cout<<endl;
return true;
}
if(j==n)
{
//go to next row
return sudokuSolver(sudoku, i+1, 0, n);
}
//check for pre-filled boxes
if(sudoku[i][j]!=0)
{ return sudokuSolver(sudoku, i, j+1, n); }
for(int number=1; number<=n; number++)
{
if(checkNumberPlacement(sudoku, i, j, n, number))
{
//assume the number is correct
sudoku[i][j] = number;
bool isCorrect = sudokuSolver(sudoku, i, j+1, n);
if(isCorrect==true){return true;}
}
}
//backtracking;
sudoku[i][j] = 0;
return false;
}
int main() {
int sudoku[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},
{9,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}
};
sudokuSolver(sudoku, 0, 0, 9);
return 0;
}