Backtracking: Return the number of queens possible in a chessboard

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