×

N Queen Problem | Return all Distinct Solutions to the N-Queens Puzzle

The n-queens is the problem of placing n queens on n × n chessboard such that no two queens can attack each other. Given an integer n, return all distinct solutions to the n -queens puzzle. Each solution contains a distinct boards configuration of the queen's placement.

Code Implementation

//Copyright © Rohan Chakravarty. All Rights Reserved.
//C++
class Solution {
public:
 vector<vector<string>> solveNQueens(int n) {
  vector<vector<string>> ans;//this vector will add all of the possible combinations board
  vector<string> board(n);
  string s(n, '.');
  for (int i = 0; i < n; i++) {
   board[i] = s;
  }
  vector<int> left(n,0),upperd(2*n-1,0),lowerD(2*n-1,0);
  solve(board,0,n,ans,left,upperd,lowerD);
  return ans;
 }

 void solve(vector<string> &board, int col,int n,vector<vector<string>> &ans,vector<int> &left,vector<int> &upperD,vector<int> &lowerD) {//OP solution
  if(col == n) {
   ans.push_back(board);
   return;
  }

  for(int row =0;row<n;row++) {
   if(left[row]==0 && upperD[(n-1)+(col-row)]==0 && lowerD[row+col]==0) {
    board[row][col]='Q';
    left[row]=1;
    upperD[(n-1)+(col-row)]=1;
    lowerD[row+col]=1;
    solve(board,col+1,n,ans,left,upperD,lowerD);
    board[row][col]='.';
    left[row]=0;
    upperD[(n-1)+(col-row)]=0;
    lowerD[row+col]=0;
   }
  }
 }

 void solve(vector<string> &board,int col,int n,vector<vector<string>> &ans) {
  if(col==n) {
   ans.push_back(board);
   return;
  }

  for(int i=0;i<n;i++) {
   if(isSafe(board,i,col,n)) {
    board[i][col]='Q';
    solve(board,col+1,n,ans);
    board[i][col]='.';
   }
  }
 }
};
            

Copy Code