Problem Statement:
You are given an n * n chessboard, you need to return the number of queens possible in the chess board.
Example
n = 4 Output = 2 You can place 2 queens such that they dont attack each other Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
Solution
we use backtracking for this solution.
We place a queen at a position and check if the position is valid.
If the position is valid, then we put another queen and check if the position is valid.
If the position is not valid, then we backtrack to another location.
Solution in C++
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<vector> #include<set> using namespace std; int _count = 0; bool check_is_valid(int matrix[][9],int row,int col,int n) { // check column for(int r=0;r<row;r++) { if(matrix[r][col]==1) return false; } // check left diagonal int i=row,j=col; while(i>=0 && j>=0) { if(matrix[i][j]==1) return false; i--;j--; } // check right diagonal i=row,j=col; while(i>=0 && j<n) { if(matrix[i][j]==1) return false; i--;j++; } return true; } void backtracking(int matrix[][9],int row,int n) { if(row == n) { _count++; return; } for(int col=0;col<n;col++) { if(check_is_valid(matrix,row,col,n)) { matrix[row][col] = 1; // if queen can be placed, mark it as 1 // now check for placement of next queen backtracking(matrix,row+1,n); //backtracking step matrix[row][col]=0; } } } int get_total_n_queen(int n) { int matrix[9][9]={0}; backtracking(matrix,0,n); return _count; } int main() { cout<<"Result = "<<get_total_n_queen(4)<<endl; return 0; }
Output:
Result = 2