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
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 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!)$
Space Complexity – Since we’ve used the 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], andcolumn[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], andcolumn[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!\,)$
Space Complexity – 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)$
Approach 3: Efficient Backtracking Approach Using 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.
- colMask – If the $i^{th}$ bit of 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.
- 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 left diagonal.
- rightDiagonalMask – 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.
Initialize all of them with a0value.
- 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 –
- colMask – If we are placing the queen in the $i^{th}$ column we will set the $i^{th}$ bit of colMask.
- leftDiagonalMask – If we place the queen in the $i^{th}$ column we will set the $i^{th}$ bit of leftDiagonalMask and shift all its bits toward left by
1as it has to block the next column of the next row (as it falls on the left diagonal). - rightDiagonalMask – If we place the queen in the $i^{th}$ column we will set the $i^{th}$ bit of rightDiagonalMask and shift all its bits toward the right by
1as 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!\,)$
Space Complexity – 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).
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.
