N Queens Problem

Let’s understand two approaches for solving this Hard leetcode Problem:-

Approach 1: Using Branch and Bound

//Using Branch and Bound Technique
class Solution {
public:
void solveNQueensHelper(int n, int row, vector<vector<string>>& output, bool* cols, bool* diag1, bool* diag2, vector<string> smallOutput){

//Base Case
if(row == n){
output.push_back(smallOutput);
return;
}

//Traversing the columns in current row
for(int col = 0; col < n; col++){
//If the current column is not bounded
if(cols[col] == false && diag1[row+col] == false && diag2[row-col+n-1] == false){
//Bound the columns
cols[col] = true;
diag1[row+col] = true;
diag2[row-col+n-1] = true;
smallOutput[row][col] = ‘Q’;
//recursively calling the column
solveNQueensHelper(n, row+1, output, cols, diag1, diag2, smallOutput);
//Now mark all the things as false so that more paths can be explored
cols[col] = false;
diag1[row+col] = false;
diag2[row-col+n-1] = false;
smallOutput[row][col] = ‘.’;
}

}

}

vector<vector<string>> solveNQueens(int n) {

//array to bound columns
bool* col = new bool[n];
//array to store diagonal
bool* diag1 = new bool[2*n-1];
//array to store reverse diagonal
bool* diag2 = new bool[2*n-1];

//Initializing the above arrays
for(int i = 0; i < n; i++){
col[i] = false;
}
for(int i = 0; i < 2*n-1; i++){
diag1[i] = false;
diag2[i] = false;
}

//storing the final Ans in it
vector<vector<string>> finalOutput;
vector<string> smallOutput;

//Making the 2-d Chess board.
for(int i = 0; i < n; i++){
string t(n, ‘.’);
smallOutput.push_back(t);
}

//calling the helper function
solveNQueensHelper(n, 0, finalOutput, col, diag1, diag2, smallOutput);
return finalOutput;
}
};

Time Complexity: O(N!)

Recurrence Relation : T(N) = N*T(N-1).

Space Complexity: O(1)

Execution time on Leetcode: 8ms

Approach 2: Using Backtracking

class Solution {
public:
bool isSafe(int row, int col, vector<string> smallOutput, int n){
//check if that column contains queen
for(int i = row-1; i >= 0; i — ){
if(smallOutput[i][col] == ‘Q’){
return false;
}
}

//check in the diagonals
for(int i = row-1, j = col-1; i >= 0 && j >= 0; i — , j — ){
if(smallOutput[i][j] == ‘Q’){
return false;
}
}

for(int i = row-1, j = col+1; i >= 0 && j < n; i — , j++){
if(smallOutput[i][j] == ‘Q’){
return false;
}
}

return true;
}

void solveNQueensHelper(int n, int row, vector<vector<string>>& output, vector<string> smallOutput){

//Base Case
if(row == n){
output.push_back(smallOutput);
return;
}

//Traversing the columns in current row
for(int col = 0; col < n; col++){
//If the current column is safe to place the queen
if(isSafe(row, col, smallOutput, n)){
smallOutput[row][col] = ‘Q’;
//recursively calling the column
solveNQueensHelper(n, row+1, output, smallOutput);
//Unmark the col so that more paths can be explored
smallOutput[row][col] = ‘.’;
}

}

}

vector<vector<string>> solveNQueens(int n) {

//storing the final Ans in it
vector<vector<string>> finalOutput;
vector<string> smallOutput;

//Making the 2-d Chess board.
for(int i = 0; i < n; i++){
string t(n, ‘.’);
smallOutput.push_back(t);
}

//calling the helper function
solveNQueensHelper(n, 0, finalOutput, smallOutput);
return finalOutput;
}
};

Time Complexity: O(N!)

Recurrence Relation : T(N) = N*T(N-1)+O(time taken in checking previous rows).

Space Complexity: O(1)

Execution Time on Leetcode: 52ms