//given n- queen problem
//state number of possible solutions
#include
using namespace std;
//creating a function to check if it is safe to place the queen at the current position
bool isSafe(int mat[][10], int i, int j, int n){
//check for all rows above the particular column
//check for left diagonal and right diagonal
for(int row=0; row<i;row++){
if(mat[row][j]==1){
return false;
}
}
//left diagonal
int x=i;
int y=j;
while(x>=0 && y>=0){
if(mat[x][y]==1){
return false;
}
x–;
y–;
}
x=i;
y=j;
while(x>=0 && y<n){
if(mat[x][y]==1){
return false;
}
x–;
y++;
}
return false;
}
//since we are solving row wise so must include i in row as we would require to call the function recursively for the next row
bool solveNQueen(int mat[][10], int i,int n){
//base case
int countt =0;
if(i==n){
countt++ ;
cout<<countt;
return false;
}
for(int j=0;j<n;j++){
if(isSafe(mat,i,j,n)){
mat[i][j] =1;
//by placing in that position check if we could recursively solve for remaining positions
bool rest = solveNQueen(mat,i+1,n);
if(rest){
return true;
}
mat[i][j] =0; //backtracking
}
}
return false;
}
int main(){
int mat[10][10]= {0};
int n;
//n 1 to 11
cin>>n;
solveNQueen(mat,0,n);
return 0;
}