## What is N Queen Problem?

The *N-Queen* is the problem of placing `n`

queens on a chessboard of dimensions $n\times n$ such that no queen can attack another queen in a single move.

### Problem Statement

We need to check if there exists such an arrangement of `n`

queens and if it exists then print the arrangement.

Note that a queen in chess can attack in any of the eight directions i.e. *left/right*, *upward/downward*, *diagonally upward/downward*.

## Examples

### Example 1 –

*Input –*`4`

*Output –*

. Q . .

. . . Q

Q . . .

. . Q .

**Explanation –**

The arrangement of queens on the chessboard looks like this –

It can be seen that no queen can attack any other queen.

### Example 2 –

*Input –*`3`

*Output –*

No Solution exists

**Explanation –**

From the above image, we can say that no arrangement exists for `n = 3`

.

## Constraints

$1\leq N \leq 12$

## Approach 1: *Backtracking* Approach

*Backtracking*

The first and the most intuitive approach is to simulate the whole process i.e. trying out all the possibilities until we’ve found a valid one. Before beginning with the algorithm to find the solution to the `N`

queens problem, let’s have a look at some observations –

- Each row of the chessboard should have exactly one queen. This is because, if there are two or more queens in a single row then they can attack each other.
- Each column of the chessboard should have exactly one queen. Again due to the same reason.

So we will try to place a queen at a valid position in each row, and then we will recur for the subsequent rows of the chessboard. If by following this method, we have placed the queens in each of the `n`

rows, it means the solution exists.

### Algorithm

The algorithm is as follows –

- Define a character array board of dimensions $N\times N$ and initialize all its entries with
`'.'`

, where`'.'`

represents the empty cell. - Start the process from the topmost row.
- If all queens are placed return true.
- Otherwise, for each of the columns in the current row do the following –
- If it is possible to place the queen in the current cell $i.e.$
*(row, col)*, place a queen in this cell. - Check if placing the queen in the current cell leads to a valid solution. If yes, then print the solution and terminate the program.
- Otherwise, remove the queen from the current cell.

- If it is possible to place the queen in the current cell $i.e.$
- If all the columns are tried for a given row, Return false to trigger the backtracking.

### Java Implementation

```
import java.util.*;
public class Main{
```*// Function to print the solution.*
static void printSolution(char board[][], int N){
*// It is similar to printing the 2-d array.*
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
*// Function to check if it is safe to place *
*// queen in the cell (row, col) such that *
*// it does not attack any other queen.*
static boolean isSafe (char board[][], int row, int col, int N){
*// Defining and initializing i and j with row *
*// and col respectively.*
int i = row, j = col;
*// Checking if the left (main) diagonal has *
*// any queen.*
while (i > -1 && j > -1){
*// If a queen is found, return 'false'*
*// that means it is not safe to place a queen.*
if (board[i][j] == 'Q')
return false;
*// Updating values of i and j*
i--;
j--;
}
i = row;
j = col;
*// Checking if the right (secondary) diagonal has *
*// any queen.*
while (i > -1 && j < N){
*// If a queen is found, return 'false'*
*// that means it is not safe to place a queen.*
if (board[i][j] == 'Q')
return false;
*// Updating values of i and j*
i--;
j++;
}
i = row;
j = col;
*// Checking if the columns (col) has *
*// any queen.*
while (i > -1){
*// If a queen is found, return 'false'*
*// that means it is not safe to place a queen.*
if (board[i][j] == 'Q')
return false;
*// Updating values of i and j*
i--;
}
*// If we have reached here, it means it is safe*
*// to place the queen in the cell (row, col);*
*// Hence, returning true*
return true;
}
*// Function to check whether solution exists*
*// for N queen problem, for the provided N.*
*// board -> Chess Board of dimensions N*N*
*// N -> Size of the chess board*
*// row -> Row number in which we will try to place *
*// the queen. It's value ranges from [0, N-1].*
static boolean solutionExists(char board[][], int N, int row){
*// If we have placed a queen in all*
*// the rows, it means solution exists.*
if (row >= N)
return true;
*// Trying to place the queen in every possible*
*// cell in the 'row th' row.*
for (int col = 0; col < N; col++){
*// Using a function to check if it is*
*// possible to place a queen in the cell*
*// (row, col) such that it does not attack*
*// any other queen.*
if(isSafe(board, row, col, N)){
*// If found true, place a queen in the *
*// cell (row, col) and recur for the*
*// next row.*
board[row][col] = 'Q';
if (solutionExists(board, N, row + 1))
return true;
*// This statement will execute only if placing queen in cell (row, col) do not *
*// form any solution. Hence, we will consider*
*// to leave this cell empty.*
board[row][col] = '.';
}
}
*// Returning false if we do not find any valid*
*// Solution.*
return false;
}
*// Function to Solve the NQueen Problem*
static void solveNQueenProblem(int N){
*// Defining the board, that will be used to print*
*// the result if a solution exists*
char board[][] = new char[N][];
*// Initializing all its cells to be empty*
*// at first.*
for(int i = 0; i < N; i++){
board[i] = new char[N];
*// '.' Represents empty cell*
Arrays.fill(board[i], '.');
}
*// If the solution do not exists*
if(!solutionExists(board, N, 0)){
System.out.println("No solution exists for N = "+ N);
}
*// Otherwise, if the solution exists.*
else{
System.out.println("One of the possible solution for N = "+N+" is - ");
printSolution(board, N);
}
}
public static void main(String[] args) {
*// Defining the dimension of square board.*
int N = 4;
*// Calling function to solve the*
*// N queen problem for the given N.*
solveNQueenProblem(N);
}
}

### C++ Implementation

```
#include<bits/stdc++.h>
using namespace std;
```*// Function to print the solution.*
void printSolution(char **board, int N){
*// It is similar to printing the 2-d array.*
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << board[i][j] << " ";
}
cout << endl;
}
}
*// Function to check if it is safe to place *
*// queen in the cell (row, col) such that *
*// it does not attack any other queen.*
bool isSafe (char **board, int row, int col, int N){
*// Defining and initializing i and j with row *
*// and col respectively.*
int i = row, j = col;
*// Checking if the left (main) diagonal has *
*// any queen.*
while (i > -1 && j > -1){
*// If a queen is found, return 'false'*
*// that means it is not safe to place a queen.*
if (board[i][j] == 'Q')
return false;
*// Updating values of i and j*
i--;
j--;
}
i = row;
j = col;
*// Checking if the right (secondary) diagonal has *
*// any queen.*
while (i > -1 && j < N){
*// If a queen is found, return 'false'*
*// that means it is not safe to place a queen.*
if (board[i][j] == 'Q')
return false;
*// Updating values of i and j*
i--;
j++;
}
i = row;
j = col;
*// Checking if the columns (col) has *
*// any queen.*
while (i > -1){
*// If a queen is found, return 'false'*
*// that means it is not safe to place a queen.*
if (board[i][j] == 'Q')
return false;
*// Updating values of i and j*
i--;
}
*// If we have reached here, it means it is safe*
*// to place the queen in the cell (row, col);*
*// Hence, returning true*
return true;
}
*// Function to check whether solution exists*
*// for N queen problem, for the provided N.*
*// board -> Chess Board of dimensions N*N*
*// N -> Size of the chess board*
*// row -> Row number in which we will try to place *
*// the queen. It's value ranges from [0, N-1].*
bool solutionExists(char **board, int N, int row){
*// If we have placed a queen in all*
*// the rows, it means solution exists.*
if (row >= N)
return true;
*// Trying to place the queen in every possible*
*// cell in the 'row th' row.*
for (int col = 0; col < N; col++){
*// Using a function to check if it is*
*// possible to place a queen in the cell*
*// (row, col) such that it does not attack*
*// any other queen.*
if(isSafe(board, row, col, N)){
*// If found true, place a queen in the *
*// cell (row, col) and recur for the*
*// next row.*
board[row][col] = 'Q';
if (solutionExists(board, N, row + 1))
return true;
*// This statement will execute only if placing queen in cell (row, col) do not *
*// form any solution. Hence, we will consider*
*// to leave this cell empty.*
board[row][col] = '.';
}
}
*// Returning false if we do not find any valid*
*// Solution.*
return false;
}
*// Function to Solve the NQueen Problem*
void solveNQueenProblem(int N){
*// Defining the board, that will be used to print*
*// the result if a solution exists*
char **board = new char*[N];
*// Initializing all its cells to be empty*
*// at first.*
for(int i = 0; i < N; i++){
board[i] = new char[N];
*// '.' Represents empty cell*
for (int j = 0; j < N; j++)
board[i][j] = '.';
}
*// If the solution do not exists*
if(!solutionExists(board, N, 0)){
cout << "No solution exists for N = " << N << endl;
}
*// Otherwise, if the solution exists.*
else{
cout << "One of the possible solution for N = "
<< N << " is - " << endl;
printSolution(board, N);
}
}
int main() {
*// Defining the dimension of square board.*
int N = 4;
*// Calling function to solve the*
*// N queen problem for the given N.*
solveNQueenProblem(N);
}

### Python Implementation

*# Python function to solve the*
*# N Queen Problem*
*# Function to print the solution.*
def printSolution(board, N):
*# It is similar to printing the 2-d array.*
for i in range(N):
for j in range(N):
print(board[i][j], end =" ")
print()
*# Function to check if it is safe to place *
*# queen in the cell (row, col) such that *
*# it does not attack any other queen.*
def isSafe (board, row, col, N):
*# Defining and initializing i and j with row *
*# and col respectively.*
i, j = row, col
*# Checking if the left (main) diagonal has *
*# any queen.*
while (i > -1 and j > -1):
*# If a queen is found, return 'false'*
*# that means it is not safe to place a queen.*
if (board[i][j] == 'Q'):
return False
*# Updating values of i and j*
i -= 1
j -= 1
i, j = row, col
*# Checking if the right (secondary) diagonal has *
*# any queen.*
while (i > -1 and j < N):
*# If a queen is found, return 'false'*
*# that means it is not safe to place a queen.*
if (board[i][j] == 'Q'):
return False
*# Updating values of i and j*
i -= 1
j += 1
i, j = row, col
*# Checking if the columns (col) has *
*# any queen.*
while (i > -1):
*# If a queen is found, return 'false'*
*# that means it is not safe to place a queen.*
if (board[i][j] == 'Q'):
return False
*# Updating values of i and j*
i -= 1
*# If we have reached here, it means it is safe*
*# to place the queen in the cell (row, col)*
*# Hence, returning true*
return True
*# Function to check whether solution exists*
*# for N queen problem, for the provided N.*
*# board -> Chess Board of dimensions N*N*
*# N -> Size of the chess board*
*# row -> Row number in which we will try to place *
*# the queen. It's value ranges from [0, N-1].*
def solutionExists(board, N, row):
*# If we have placed a queen in all*
*# the rows, it means solution exists.*
if (row >= N):
return True
*# Trying to place the queen in every possible*
*# cell in the 'row th' row.*
for col in range(N):
*# Using a function to check if it is*
*# possible to place a queen in the cell*
*# (row, col) such that it does not attack*
*# any other queen.*
if (isSafe(board, row, col, N)):
*# If found true, place a queen in the *
*# cell (row, col) and recur for the*
*# next row.*
board[row][col] = 'Q'
if (solutionExists(board, N, row + 1)):
return True
*# This statement will execute only if placing queen in cell (row, col) do not *
*# form any solution. Hence, we will consider*
*# to leave this cell empty.*
board[row][col] = '.'
*# Returning false if we do not find any valid*
*# Solution.*
return False
*# Function to Solve the NQueen Problem*
def solveNQueenProblem(N):
*# Defining the board, that will be used to print*
*# the result if a solution exists*
board = []
*# Initializing all its cells to be empty*
*# at first.*
for i in range(N):
temp = []
*# '.' Represents empty cell*
for j in range(N):
temp.append('.')
board.append(temp)
*# If the solution do not exists*
if (solutionExists(board, N, 0) == False):
print("No solution exists for N =", N)
*# Otherwise, if the solution exists.*
else:
print("One of the possible solution for N =", N, "is -")
printSolution(board, N)
*# Driver Code *
*# Defining the dimension of square board.*
N = 4
*# Calling function to solve the*
*# N queen problem for the given N.*
solveNQueenProblem(N)

**Output –**

```
One of the possible solution for N = 4 is -
. Q . .
. . . Q
Q . . .
. . Q .
```

### Complexity Analysis

** Time Complexity –** Since in each row we are iterating for $N$ times and it costs O(1) time to check if placing the queen in a cell is valid. Therefore, the recurrence relation of the above algorithm is $T(N)=$ $N\times T(N-1) + N$ which evaluates to $O(N \times N!)$

**Since we’ve used the**

*Space Complexity –**board*array which is of dimensions $N\times N$, the space complexity is $O(N^2)$

## Approach 2: Backtracking with Optimization in isSafe() function

In our last code, we have seen that for each cell on the board we were spending $O(N)$ time just to check if placing the queen in an arbitrary cell is valid or not using the `isSafe()`

function.

The idea is to optimize this `isSafe()`

function by using some mathematical phenomenon. Let’s see what they are –

Along any left diagonal, the difference between the row index and column index is constant and different for each diagonal.

Along any right diagonal the sum of the row index and column index is constant and different for each diagonal.

Now, it is clear that, if at any diagonal a queen is placed then we can not place any other queen on the same diagonal. So, instead of searching along the length of the diagonal every time, we will mark the diagonal if a queen is placed on it. The same goes with the column, due to which we will be able to perform the `isSafe()`

function in $O(1)$ time.

From the image given above, it can be observed that the difference between the row index and column index for a board is in the range of `[-( N - 1 ), ( N - 1 )]`

and if we use a boolean type array to mark diagonals we will be in trouble because array indices are non-negative. Therefore, to mark the left diagonal we will add an offset `N - 1`

to each value to make the index non-negative.

### Algorithm

The algorithm and the code for finding the answer will be the same as the previous approach. The below-given algorithm shows the optimizations made to mark the diagonal.

- Define three boolean type arrays Viz.
*leftDiagonal*,*rightDiagonal*, and*column*of size $2\times N$ each to store information about the left diagonals, right diagonals, and the columns. - To check if a cell
*(row, col)*is safe to place a queen. We will check if all the`leftDiagonal[row - col + N -1]`

,`rightDiagonal[row + col]`

, and`column[col]`

are unmarked $i.e.$*False*. - Whenever we are placing a queen in the cell
*(row, col)*, we will mark`leftDiagonal[row - col + N - 1]`

,`rightDiagonal[row + col]`

, and`column[col]`

as*True*. - When we backtrack we will again set the above value to be
*False*.

### Java Implementation

```
import java.util.*;
public class Main{
```*// Boolean arrays to store information*
*// about the placed queens.*
static boolean leftDiagonal[];
static boolean rightDiagonal[];
static boolean column[];
*// Function to print the solution.*
static void printSolution(char board[][], int N){
*// It is similar to printing the 2-d array.*
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
*// Function to check if it is safe to place *
*// queen in the cell (row, col) such that *
*// it does not attack any other queen.*
static boolean isSafe (char board[][], int row, int col, int N){
*// Checking if leftDiagonal contains a queen OR*
*// rightDiagonal contains a queen OR*
*// curretnColumns contains a queen.*
if(leftDiagonal[row - col + N - 1] ||
rightDiagonal[row + col] ||
column[col]){
return false;
}
return true;
}
*// Function to check whether solution exists*
*// for N queen problem, for the provided N.*
*// board -> Chess Board of dimensions N*N*
*// N -> Size of the chess board*
*// row -> Row number in which we will try to place *
*// the queen. It's value ranges from [0, N-1].*
static boolean solutionExists(char board[][], int N, int row){
*// If we have placed a queen in all*
*// the rows, it means solution exists.*
if (row >= N)
return true;
*// Trying to place the queen in every possible*
*// cell in the 'row th' row.*
for (int col = 0; col < N; col++){
*// Using a function to check if it is*
*// possible to place a queen in the cell*
*// (row, col) such that it does not attack*
*// any other queen.*
if(isSafe(board, row, col, N)){
*// If found true, place a queen in the *
*// cell (row, col) and recur for the*
*// next row.*
leftDiagonal[row - col + N - 1] = true;
rightDiagonal[row + col] = true;
column[col] = true;
board[row][col] = 'Q';
if (solutionExists(board, N, row + 1))
return true;
*// This statement will execute only if placing queen in cell (row, col) do not *
*// form any solution. Hence, we will consider*
*// to leave this cell empty.*
board[row][col] = '.';
leftDiagonal[row - col + N - 1] = false;
rightDiagonal[row + col] = false;
column[col] = false;
}
}
*// Returning false if we do not find any valid*
*// Solution.*
return false;
}
*// Function to Solve the NQueen Problem*
static void solveNQueenProblem(int N){
*// Defining the board, that will be used to print*
*// the result if a solution exists*
char board[][] = new char[N][];
*// Initializing all its cells to be empty*
*// at first.*
for(int i = 0; i < N; i++){
board[i] = new char[N];
*// '.' Represents empty cell*
Arrays.fill(board[i], '.');
}
*// Initializing boolean arrays.*
leftDiagonal = new boolean[2*N];
rightDiagonal = new boolean[2*N];
column = new boolean[N];
*// If the solution do not exists*
if(!solutionExists(board, N, 0)){
System.out.println("No solution exists for N = "+ N);
}
*// Otherwise, if the solution exists.*
else{
System.out.println("One of the possible solution for N = "+N+" is - ");
printSolution(board, N);
}
}
public static void main(String[] args) {
*// Defining the dimension of square board.*
int N = 4;
*// Calling function to solve the*
*// N queen problem for the given N.*
solveNQueenProblem(N);
}
}

### C++ Implementation

```
#include<bits/stdc++.h>
using namespace std;
```*// Boolean arrays to store information*
*// about the placed queens.*
bool *leftDiagonal;
bool *rightDiagonal;
bool *column;
*// Function to print the solution.*
void printSolution(char **board, int N){
*// It is similar to printing the 2-d array.*
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << board[i][j] << " ";
}
cout << endl;
}
}
*// Function to check if it is safe to place *
*// queen in the cell (row, col) such that *
*// it does not attack any other queen.*
bool isSafe (char **board, int row, int col, int N){
*// Checking if leftDiagonal contains a queen OR*
*// rightDiagonal contains a queen OR*
*// curretnColumns contains a queen.*
if(leftDiagonal[row - col + N - 1] ||
rightDiagonal[row + col] ||
column[col]){
return false;
}
return true;
}
*// Function to check whether solution exists*
*// for N queen problem, for the provided N.*
*// board -> Chess Board of dimensions N*N*
*// N -> Size of the chess board*
*// row -> Row number in which we will try to place *
*// the queen. It's value ranges from [0, N-1].*
bool solutionExists(char **board, int N, int row){
*// If we have placed a queen in all*
*// the rows, it means solution exists.*
if (row >= N)
return true;
*// Trying to place the queen in every possible*
*// cell in the 'row th' row.*
for (int col = 0; col < N; col++){
*// Using a function to check if it is*
*// possible to place a queen in the cell*
*// (row, col) such that it does not attack*
*// any other queen.*
if(isSafe(board, row, col, N)){
*// If found true, place a queen in the *
*// cell (row, col) and recur for the*
*// next row.*
leftDiagonal[row - col + N - 1] = true;
rightDiagonal[row + col] = true;
column[col] = true;
board[row][col] = 'Q';
if (solutionExists(board, N, row + 1))
return true;
*// This statement will execute only if placing queen in cell (row, col) do not *
*// form any solution. Hence, we will consider*
*// to leave this cell empty.*
board[row][col] = '.';
leftDiagonal[row - col + N - 1] = false;
rightDiagonal[row + col] = false;
column[col] = false;
}
}
*// Returning false if we do not find any valid*
*// Solution.*
return false;
}
*// Function to Solve the NQueen Problem*
void solveNQueenProblem(int N){
*// Defining the board, that will be used to print*
*// the result if a solution exists*
char **board = new char*[N];
*// Initializing all its cells to be empty*
*// at first.*
for(int i = 0; i < N; i++){
board[i] = new char[N];
*// '.' Represents empty cell*
for (int j = 0; j < N; j++)
board[i][j] = '.';
}
*// Initializing boolean arrays.*
leftDiagonal = new bool[2*N];
rightDiagonal = new bool[2*N];
column = new bool[N];
*// If the solution do not exists*
if(!solutionExists(board, N, 0)){
cout << "No solution exists for N = " << N << endl;
}
*// Otherwise, if the solution exists.*
else{
cout << "One of the possible solution for N = "
<< N << " is - " << endl;
printSolution(board, N);
}
}
int main() {
*// Defining the dimension of square board.*
int N = 4;
*// Calling function to solve the*
*// N queen problem for the given N.*
solveNQueenProblem(N);
}

### Python Implementation

*# Python function to solve the*
*# N Queen Problem*
*# Boolean arrays to store information*
*# about the placed queens.*
leftDiagonal = [False]*30
rightDiagonal = [False]*30
column = [False]*15
*# Function to print the solution.*
def printSolution(board, N):
*# It is similar to printing the 2-d array.*
for i in range(N):
for j in range(N):
print(board[i][j], end =" ")
print()
*# Function to check if it is safe to place *
*# queen in the cell (row, col) such that *
*# it does not attack any other queen.*
def isSafe (board, row, col, N):
*# Checking if leftDiagonal contains a queen OR*
*# rightDiagonal contains a queen OR*
*# curretnColumns contains a queen.*
if(leftDiagonal[row - col + N - 1] or
rightDiagonal[row + col] or
column[col]):
return False
return True
*# Function to check whether solution exists*
*# for N queen problem, for the provided N.*
*# board -> Chess Board of dimensions N*N*
*# N -> Size of the chess board*
*# row -> Row number in which we will try to place *
*# the queen. It's value ranges from [0, N-1].*
def solutionExists(board, N, row):
*# If we have placed a queen in all*
*# the rows, it means solution exists.*
if (row >= N):
return True
*# Trying to place the queen in every possible*
*# cell in the 'row th' row.*
for col in range(N):
*# Using a function to check if it is*
*# possible to place a queen in the cell*
*# (row, col) such that it does not attack*
*# any other queen.*
if (isSafe(board, row, col, N)):
*# If found true, place a queen in the *
*# cell (row, col) and recur for the*
*# next row.*
leftDiagonal[row - col + N - 1] = True
rightDiagonal[row + col] = True
column[col] = True
board[row][col] = 'Q'
if (solutionExists(board, N, row + 1)):
return True
*# This statement will execute only if placing queen in cell (row, col) do not *
*# form any solution. Hence, we will consider*
*# to leave this cell empty.*
board[row][col] = '.'
leftDiagonal[row - col + N - 1] = False
rightDiagonal[row + col] = False
column[col] = False
*# Returning false if we do not find any valid*
*# Solution.*
return False
*# Function to Solve the NQueen Problem*
def solveNQueenProblem(N):
*# Defining the board, that will be used to print*
*# the result if a solution exists*
board = []
*# Initializing all its cells to be empty*
*# at first.*
for i in range(N):
temp = []
*# '.' Represents empty cell*
for j in range(N):
temp.append('.')
board.append(temp)
*# If the solution do not exists*
if (solutionExists(board, N, 0) == False):
print("No solution exists for N =", N)
*# Otherwise, if the solution exists.*
else:
print("One of the possible solution for N =", N, "is -")
printSolution(board, N)
*# Driver Code *
*# Defining the dimension of square board.*
N = 4
*# Calling function to solve the*
*# N queen problem for the given N.*
solveNQueenProblem(N)

**Output –**

```
One of the possible solution for N = 4 is -
. Q . .
. . . Q
Q . . .
. . Q .
```

### Complexity Analysis

** Time Complexity –** Since in each row we are iterating for N times and it costs $O(1)$ time to check if placing the queen in a cell is valid. Therefore, the recurrence relation of the above algorithm is $T(N)= N\times T(N-1)$ which evaluates to $O(N!\,)$

**We have used a 2-d array of dimension $N\times N$ to store the board elements, also we have used three boolean arrays of length $\theta(N)$ each. Therefore, the total space complexity is $O(N^2 + 2N + 2N + N) = O(N^2)$**

*Space Complexity –*## Approach 3: Efficient Backtracking Approach Using *Bit-Masking*

*Bit-Masking*

In the previous approaches, we have seen that each row and column can contain at most one queen. To place a queen at any cell in the board, we must check if it attacks any other queen and check that we have used boolean arrays in our last approach.

But, as per the given constraints $1\leq N\leq 12$ we can also use the *bitmask* approach to saving space required in boolean arrays. In this approach, we will be replacing the boolean arrays with `32`

-bit integers so that we can achieve the solution in constant extra space.

Let’s see what is this *bitmask* approach –

- Define three integers which we will use to identify the safe columns to place the queen in each row.
If the $i^{th}$ bit of*colMask –**colMask*is set, then it means it is unsafe to place a queen in the $i^{th}$ column as it can be attacked by a queen placed somewhere in the same column.If the $i^{th}$ bit is set, then it means it is unsafe to place a queen in the $i^{th}$ column as it can be attacked by a queen placed somewhere in the left diagonal.*leftDiagonalMask –*If the $i^{th}$ bit is set, then it means it is unsafe to place a queen in the $i^{th}$ column as it can be attacked by a queen placed somewhere in the right diagonal.*rightDiagonalMask –*

Initialize all of them with a`0`

value.

- Now, to check if a cell
*(row, col)*is safe to place the queen, we check if the $col^{th}$ bit of anyone of the mask values is set. If found yes, then it is unsafe to place the queen in the cell. - When we place the queen in a cell
*(row, col)*we need to modify the mask value to mark the newly formed unsafe cells in the next column (due to placing the queen in the cell). We will modify as per the following points –If we are placing the queen in the $i^{th}$ column we will set the $i^{th}$ bit of*colMask –**colMask*.If we place the queen in the $i^{th}$ column we will set the $i^{th}$ bit of*leftDiagonalMask –**leftDiagonalMask*and shift all its bits toward left by`1`

as it has to block the next column of the next row (as it falls on the left diagonal).If we place the queen in the $i^{th}$ column we will set the $i^{th}$ bit of*rightDiagonalMask –**rightDiagonalMask*and shift all its bits toward the right by`1`

as it has to block the previous column of the next row (as it falls on the left diagonal).

### Java Implementation

```
import java.util.*;
public class Main{
```*// Function to print the solution.*
static void printSolution(char board[][], int N){
*// It is similar to printing the 2-d array.*
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
*// Function to check whether solution exists*
*// for N queen problem, for the provided N.*
*// board -> Chess Board of dimensions N*N*
*// N -> Size of the chess board*
*// row -> Row number in which we will try to place *
*// the queen. It's value ranges from [0, N-1].*
*// colMask -> Set bits of colMask denote the unsafe columns*
*// due to the presence of queen in the column.*
*// leftDiagonalMask -> Set bits of leftDiagonalMask denote the unsafe columns*
*// due to the presence of queen in the left diagonal.*
*// rightDiagonalMask -> Set bits of rightDiagonalMask denote the unsafe columns*
*// due to the presence of queen in the right diagonal.*
static boolean solutionExists(char board[][], int N, int row,
int colMask, int leftDiagonalMask, int rightDiagonalMask){
*// If we have filled all the rows*
*// return true. *
if (row>=N)
return true;
*// Using colMask, leftDiagonalMask and*
*// rightDiagonal mask find the columns in which *
*// queen can be placed.*
int safe = ((1 << N) - 1) &
(~ (colMask |
leftDiagonalMask |
rightDiagonalMask));
*// Iterate till safe >0 i.e. iterating *
*// for all the safe columns.*
while (safe > 0){
*// Extract the rightmost safe columns i.e.*
*// the leftmost column in which queen can*
*// be placed.*
int mask = safe & (-safe);
*// Now to find the column index we need to find*
*// log_2 of mask.*
int leftMostCol = (int)(Math.log(mask) /
Math.log(2));
*// Place the queen in the cell.*
board[row][leftMostCol] = 'Q';
*// Recur fo the next row after modifying the bit masks value.*
if (solutionExists(board, N, row + 1, colMask | mask,
(leftDiagonalMask | mask) << 1, (rightDiagonalMask | mask) >> 1)){
return true;
}
*// Reset the rightmost set bit of the 'safe'.*
safe = safe & (safe - 1);
*// Backtrack*
board[row][leftMostCol] = '.';
}
*// Returning false at last*
return false;
}
*// Function to Solve the NQueen Problem*
static void solveNQueenProblem(int N){
*// Defining the board, that will be used to print*
*// the result if a solution exists*
char board[][] = new char[N][];
*// Initializing all its cells to be empty*
*// at first.*
for(int i = 0; i < N; i++){
board[i] = new char[N];
*// '.' Represents empty cell*
Arrays.fill(board[i], '.');
}
*// If the solution do not exists*
if(!solutionExists(board, N, 0, 0, 0, 0)){
System.out.println("No solution exists for N = " + N);
}
*// Otherwise, if the solution exists.*
else{
System.out.println("One of the possible solution for N = " + N + " is - ");
printSolution(board, N);
}
}
public static void main(String[] args) {
*// Defining the dimension of square board.*
int N = 4;
*// Calling function to solve the*
*// N queen problem for the given N.*
solveNQueenProblem(N);
}
}

### C++ Implementation

```
#include<bits/stdc++.h>
using namespace std;
```*// Function to print the solution.*
void printSolution(vector<vector<char>> board, int N){
*// It is similar to printing the 2-d array.*
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cout << board[i][j] << " ";
}
cout << endl;
}
}
*// Function to check whether solution exists*
*// for N queen problem, for the provided N.*
*// board -> Chess Board of dimensions N*N*
*// N -> Size of the chess board*
*// row -> Row number in which we will try to place *
*// the queen. It's value ranges from [0, N-1].*
*// colMask -> Set bits of colMask denote the unsafe columns*
*// due to the presence of queen in the column.*
*// leftDiagonalMask -> Set bits of leftDiagonalMask denote the unsafe columns*
*// due to the presence of queen in the left diagonal.*
*// rightDiagonalMask -> Set bits of rightDiagonalMask denote the unsafe columns*
*// due to the presence of queen in the right diagonal.*
bool solutionExists(vector<vector<char>> &board, int N, int row,
int colMask, int leftDiagonalMask, int rightDiagonalMask){
*// If we have filled all the rows*
*// return true. *
if (row >= N)
return true;
*// Using colMask, leftDiagonalMask and*
*// rightDiagonal mask find the columns in which *
*// queen can be placed.*
int safe = ((1 << N) - 1) &
(~ (colMask |
leftDiagonalMask |
rightDiagonalMask));
*// Iterate till safe >0 i.e. iterating *
*// for all the safe columns.*
while (safe > 0){
*// Extract the rightmost safe columns i.e.*
*// the leftmost column in which queen can*
*// be placed.*
int mask = safe & (-safe);
*// Now to find the column index we need to find*
*// log_2 of mask.*
int leftMostCol = (int)(log2(mask));
*// Place the queen in the cell.*
board[row][leftMostCol] = 'Q';
*// Recur fo the next row after modifying the bit masks value.*
if (solutionExists(board, N, row + 1, colMask | mask,
(leftDiagonalMask | mask) << 1, (rightDiagonalMask | mask) >> 1)){
return true;
}
*// Reset the rightmost set bit of the 'safe'.*
safe = safe & (safe - 1);
*// Backtrack*
board[row][leftMostCol] = '.';
}
*// Returning false at last*
return false;
}
*// Function to Solve the NQueen Problem*
void solveNQueenProblem(int N){
*// Defining the board, that will be used to print*
*// the result if a solution exists*
vector<vector<char>> board;
board.resize(N);
*// Initializing all its cells to be empty*
*// at first.*
for(int i = 0; i < N; i++){
*// '.' Represents empty cell*
for(int j = 0; j < N; j++)
board[i].push_back('.');
}
*// If the solution do not exists*
if(!solutionExists(board, N, 0, 0, 0, 0)){
cout << "No solution exists for N = " << N;
}
*// Otherwise, if the solution exists.*
else{
cout << "One of the possible solution for N = "
<< N << " is - " << endl;
printSolution(board, N);
}
}
int main() {
*// Defining the dimension of square board.*
int N = 4;
*// Calling function to solve the*
*// N queen problem for the given N.*
solveNQueenProblem(N);
}

### Python Implementation

```
import math
```*# Function to print the solution.*
def printSolution(board, N):
*# It is similar to printing the 2-d array.*
for i in range(N):
for j in range(N):
print(board[i][j], end = " ")
print()
*# Function to check whether solution exists*
*# for N queen problem, for the provided N.*
*# board -> Chess Board of dimensions N*N*
*# N -> Size of the chess board*
*# row -> Row number in which we will try to place *
*# the queen. It's value ranges from [0, N-1].*
*# colMask -> Set bits of colMask denote the unsafe columns*
*# due to the presence of queen in the column.*
*# leftDiagonalMask -> Set bits of leftDiagonalMask denote the unsafe columns*
*# due to the presence of queen in the left diagonal.*
*# rightDiagonalMask -> Set bits of rightDiagonalMask denote the unsafe columns*
*# due to the presence of queen in the right diagonal.*
def solutionExists(board, N, row, colMask, leftDiagonalMask, rightDiagonalMask):
*# If we have filled all the rows*
*# return true. *
if (row >= N):
return True
*# Using colMask, leftDiagonalMask and*
*# rightDiagonal mask find the columns in which *
*# queen can be placed.*
safe = ((1 << N) - 1) & \
(~ (colMask | \
leftDiagonalMask | \
rightDiagonalMask))
*# Iterate till safe >0 i.e. iterating *
*# for all the safe columns.*
while (safe > 0):
*# Extract the rightmost safe columns i.e.*
*# the leftmost column in which queen can*
*# be placed.*
mask = safe & (-safe)
*# Now to find the column index we need to find*
*# log_2 of mask.*
leftMostCol = (int(math.log(mask, 2)))
*# Place the queen in the cell.*
board[row][leftMostCol] = 'Q'
*# Recur fo the next row after modifying the bit masks value.*
if (solutionExists(board, N, row + 1, colMask | mask,
(leftDiagonalMask | mask) << 1, (rightDiagonalMask | mask) >> 1)):
return True
*# Reset the rightmost set bit of the 'safe'.*
safe = safe & (safe - 1)
*# Backtrack*
board[row][leftMostCol] = '.'
*# Returning false at last*
return False
*# Function to Solve the NQueen Problem*
def solveNQueenProblem(N):
*# Defining the board, that will be used to print*
*# the result if a solution exists*
board = []
*# Initializing all its cells to be empty*
*# at first.*
for i in range(N):
board.append([])
*# '.' Represents empty cell*
for j in range(N):
board[i].append('.')
*# If the solution do not exists*
if(solutionExists(board, N, 0, 0, 0, 0) == False):
print("No solution exists for N = ", N)
*# Otherwise, if the solution exists.*
else:
print("One of the possible solution for N =", N, "is -")
printSolution(board, N)
*# Drive Code*
*# Defining the dimension of square board.*
N = 4
*# Calling function to solve the*
*# N queen problem for the given N.*
solveNQueenProblem(N)

**Output –**

```
One of the possible solution for N = 4 is -
. Q . .
. . . Q
Q . . .
. . Q .
```

### Complexity Analysis –

** Time Complexity –** Since in each row we are iterating for N times and it costs

**O(1)**time to check if placing the queen in a cell is valid. Therefore, the recurrence relation of the above algorithm is $T(N)=$ $N\times T(N-1)$ which evaluates to $O(N!\,)$

**Since, we are using a 2-dimensional array of dimension $N\times N$, therefore the overall time complexity is $O(N^2)$. However, we can say that constant extra space is required to find the answer (if we do not account space needed to store the answer).**

*Space Complexity –*## Conclusion

- N Queen problem is a classical puzzle that beautifully develops the concept of
.`Backtracking`

- The time complexity of the brute force backtracking algorithm is $O(N\times N!\,)$. However, using
*bitmasking*the time complexity can be optimized to $O(N!)$. - The space complexity irrespective of the approach is $O(N^2)$ because we need to print a
`2`

-dimensional array as the answer.