Last Updated on July 20, 2023 by Mayank Dham
The backtracking algorithm is used to solve the N queen problem, in which the board is recursively filled with queens, one at a time, and backtracked if no valid solution is found. At each step, the algorithm checks to see if the newly placed queen conflicts with any previously placed queens, and if so, it backtracks. The process is repeated until all N queens are placed on the board without conflict, or until all possible solutions are exhausted. The resulting board is a correct solution to the N queen problem.
What is Backtracking?
Backtracking is a problem-solving technique that involves recursively trying out different solutions to a problem, and backtracking or undoing previous choices when they don’t lead to a valid solution. It is commonly used in algorithms that search for all possible solutions to a problem, such as the famous eight-queens puzzle. Backtracking is a powerful and versatile technique that can be used to solve a wide range of problems.
Backtracking is often used in constraint satisfaction problems, such as the N Queen problem, where we need to find a solution that satisfies a set of constraints. In these problems, we start by choosing a value for one of the variables and checking if it satisfies the constraints. If it does, we move on to the next variable and repeat the process. If the current value does not satisfy the constraints, we backtrack to the previous variable and try a different value.
Backtracking is an effective technique for solving problems, as it allows us to incrementally build a solution and avoids the need to consider all possible solutions from scratch. However, it can also be time-consuming, as it requires many iterations and checks. To make backtracking more efficient, various optimization techniques, such as constraint propagation and heuristics, can be used.
What is N Queen Problem Algorithm?
The N-Queens Problem is a chess puzzle in which N chess queens must be placed on a NxN chessboard so that no two queens threaten each other. It has received extensive research in computer science and mathematics, and it is frequently used as a standard for evaluating algorithms and heuristics. The problem has a long history and practical applications in scheduling, data encryption, and pattern recognition.
For example, the two possible solutions to the 4 Queen problem are shown below:
The N Queen problem can be solved by using various approaches, such as brute force, backtracking, and genetic algorithms. Backtracking is one of the popular approaches for solving the N Queen problem, and it is simple to implement and can be made more efficient with optimization techniques.
N-Queen Algorithm
The complete algorithm for the N queen problem is discussed below :
- Start in the leftmost column
- If all queens are placed, return true
- Try all rows in the current column. For each row:
- a. If the queen can be placed safely in this row, mark this cell and recursively try placing the rest of the queen
- b. If placing the queen in this row leads to an unsafe configuration, unmark the cell and try the next row
- If all rows have been tried and nothing worked, return false to trigger backtracking
Approaches to Solve N Queen Problem
Below we have discussed approaches to solve the N Queen Problem
Approach 1: Naive Approach to Solve N Queen Problem
In this approach, we generate all possible queen configurations on board and print a configuration that satisfies the given constraints.
Below is the pseudo-code for Naive Approach
while there are unexplored configurations.
{
generate the next configuration
if queens don't attack in this configuration then
{
print this configuration;
}
}Approach 2: Solving N Queen Problem using backtracking
By using backtracking we position queens in different columns one by one, beginning with the leftmost column. When we position a queen in a column, we look for clashes with other queens that have already been placed. If we locate a row in the current column with no collision, we mark this row and column as part of the solution. We backtrack and return false if we cannot discover such a row due to clashes.
Algorithm:
Here’s an algorithm to solve the n queen problem:
- Start with an empty chessboard of size n x n.
- Place the first queen in the top-left corner of the board (i.e., row 1, column 1).
- Move to the next row and try to place a queen in each column until a valid position is found or all columns have been tried.
- If a valid position is found, move to the next row and repeat step 3.
- If all columns have been tried in the current row without finding a valid position, backtrack to the previous row and move the queen to the next column in that row. Repeat step 3.
- If all rows have been tried without finding a solution, backtrack to the previous row and move the queen to the next column in that row. Repeat step 3.
- If a solution is found, print the positions of the queens on the board and exit the program.
#include <bits/stdc++.h>
#define N 4
using namespace std;
void printBoard(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if(board[i][j])
cout << "Q ";
else cout<<". ";
cout<<endl;
}
}
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
// A recursive function to solve N Queen problem
bool solveNQ(int board[N][N], int col)
{
// base case
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recursively try to place rest of the queens */
if (solveNQ(board, col + 1))
return true;
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
bool solve()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQ(board, 0) == false) {
cout << "No Possible Solution exist";
return false;
}
printBoard(board);
return true;
}
int main()
{
solve();
return 0;
} import java.util.*;
import java.lang.*;
import java.io.*;
class PrepBytes {
final int N = 4;
void printBoard(int board[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if(board[i][j]==1)
System.out.print("Q ");
else
System.out.print(". ");
System.out.println();
}
}
boolean isSafe(int board[][], int row, int col)
{
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
/* Check upper diagonal on left side */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
/* Check lower diagonal on left side */
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
boolean solveNQ(int board[][], int col)
{
// base case
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
/* Check if the queen can be placed on
board[i][col] */
if (isSafe(board, i, col)) {
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recursively try to place rest of the queens */
if (solveNQ(board, col + 1) == true)
return true;
board[i][col] = 0; // Backtracking
}
}
return false;
}
boolean solve()
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQ(board, 0) == false) {
System.out.print("No Possible Solution exist");
return false;
}
printBoard(board);
return true;
}
public static void main(String args[])
{
PrepBytes Queen = new PrepBytes();
Queen.solve();
}
} global N
N = 4
def printBoard(board):
for i in range(N):
for j in range(N):
print(board[i][j], end = " ")
print()
def isSafe(board, row, col):
# Check this row on left side
for i in range(col):
if board[row][i] == 1:
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1),
range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check lower diagonal on left side
for i, j in zip(range(row, N, 1),
range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solveNQ(board, col):
# base case
if col >= N:
return True
# Consider this column and try placing
# this queen in all rows one by one
for i in range(N):
if isSafe(board, i, col):
# Place this queen in board[i][col]
board[i][col] = 1
# recursively try to place rest of the queens
if solveNQ(board, col + 1) == True:
return True
# backtracking
board[i][col] = 0
return False
def solve():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0] ]
if solveNQ(board, 0) == False:
print ("No Possible Solution exists")
return False
printBoard(board)
return True
solve() Output:
. . Q .
Q . . .
. . . Q
. Q . . Time Complexity: O(N * N!)
Space Complexity: O(N^2)
Dry Run of Approach 2 N Queen Problem
Let’s do a dry run of the N Queen problem for N=4
- Place the queen in the leftmost column.
- Place the second queen in the second column such that it cannot attack the queen in the first column.
-
Place the third queen in the third column so that it cannot attack the queen in the first two columns. No such placement is possible, so backtrack to the second column.
-
Place the second queen in another safe cell in the second column.
- Place the third queen in a safe cell in the third column.
-
Place the fourth queen in the adjacent columns so that it cannot attack the queen in the first three columns. No such placement is possible, so backtrack to the third column.
-
Place the third queen in another safe cell in the third column. There is no other safe cell for the queen in column 3, so backtrack.
-
There is no other safe cell for the queen in column 2, so backtrack to the first column.
-
Place the first queen in the next safe cell in the first column.
- Place the second queen in a safe cell in the second column.
- Place the third queen in a safe cell in the third column.
-
Place the fourth queen in a safe cell in the fourth column.
-
Finally, we have our solution!
Approach 3: Backtracking with optimization
The reason behind the N queen problem approach is that instead of checking every element in the right and left diagonals, we can use the property of diagonals:
- For each right diagonal, the sum of I and j is constant and unique, where i represents row and j represents a column in the chess board.
- The difference between i and j is constant and unique for each left diagonal, where i and j represent the row and column of the chess board, respectively.
#include<bits/stdc++.h>
using namespace std;
#define N 4
/* leftD is an array where its indices indicate row-col+N-1
(N-1) is for shifting the difference to store negative
indices */
int leftD[30] = { 0 };
/* rightD is an array where its indices indicate row+col
and used to check whether a queen can be placed on
right diagonal or not*/
int rightD[30] = { 0 };
/*column array where its indices indicates column and
used to check whether a queen can be placed in that
row or not*/
int col[30] = { 0 };
void print(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if(board[i][j]==1){
cout<<"Q ";
}
else{
cout<<". ";
}
cout<<endl;
}
}
bool solveNQ(int board[N][N], int j)
{
// base case
if (j >= N)
return true;
for (int i = 0; i < N; i++) {
/* Here we are checking if a queen can be placed on
board[row][col]. We just need to check
left[row-col+n-1] and right[row+coln] where
left and right are for left and right
diagonal respectively*/
if ((leftD[i - j + N - 1] != 1 && rightD[i + j] != 1) && col[i] != 1) {
board[i][j] = 1;
leftD[i - j + N - 1] = rightD[i + j] = col[i] = 1;
if (solveNQ(board, j + 1))
return true;
board[i][j] = 0; // Backtracking
leftD[i - j + N - 1] = rightD[i + j] = col[i] = 0;
}
}
return false;
}
bool solve()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQ(board, 0) == false) {
cout<<"No Possible Configuration exists";
return false;
}
print(board);
return true;
}
int main()
{
solve();
return 0;
} import java.util.*;
class PrepBytes
{
static int N = 4;
/* ld is an array where its indices indicate row-col+N-1
(N-1) is for shifting the difference to store negative
indices */
static int []ld = new int[30];
/* rd is an array where its indices indicate row+col
and used to check whether a queen can be placed on
right diagonal or not*/
static int []rd = new int[30];
/*column array where its indices indicates column and
used to check whether a queen can be placed in that
row or not*/
static int []cl = new int[30];
static void printSol(int board[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(board[i][j] + " ");
System.out.println();
}
}
static boolean solveNQ(int board[][], int col)
{
// base case
if (col >= N)
return true;
/* Consider this column and try placing
this queen in all rows one by one */
for (int i = 0; i < N; i++)
{
/* Check if the queen can be placed on
board[i][col] */
/* A check if a queen can be placed on
board[row][col].We just need to check
ld[row-col+n-1] and rd[row+coln] where
ld and rd are for left and right
diagonal respectively*/
if ((ld[i - col + N - 1] != 1 &&
rd[i + col] != 1) && cl[i] != 1)
{
/* Place this queen in board[i][col] */
board[i][col] = 1;
ld[i - col + N - 1] =
rd[i + col] = cl[i] = 1;
/* recursively try to place rest of the queens */
if (solveNQ(board, col + 1))
return true;
board[i][col] = 0; // Backtrack
ld[i - col + N - 1] =
rd[i + col] = cl[i] = 0;
}
}
return false;
}
static boolean solve()
{
int board[][] = {{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }};
if (solveNQ(board, 0) == false)
{
System.out.printf("No Possible Solution exist");
return false;
}
printSol(board);
return true;
}
public static void main(String[] args)
{
solve();
}
} N = 4
""" ld is an array where its indices indicate row-col+N-1
(N-1) is for shifting the difference to store negative
indices """
ld = [0] * 30
""" rd is an array where its indices indicate row+col
and used to check whether a queen can be placed on
right diagonal or not"""
rd = [0] * 30
"""column array where its indices indicates column and
used to check whether a queen can be placed in that
row or not"""
cl = [0] * 30
def printSol(board):
for i in range(N):
for j in range(N):
print(board[i][j], end = " ")
print()
def solveNQ(board, col):
if (col >= N):
return True
for i in range(N):
""" Check if the queen can be placed on board[i][col] """
""" A check if a queen can be placed on board[row][col].
We just need to check ld[row-col+n-1] and rd[row+coln]
where ld and rd are for left and right diagonal respectively"""
if ((ld[i - col + N - 1] != 1 and
rd[i + col] != 1) and cl[i] != 1):
""" Place this queen in board[i][col] """
board[i][col] = 1
ld[i - col + N - 1] = rd[i + col] = cl[i] = 1
""" recur to place rest of the queens """
if (solveNQ(board, col + 1)):
return True
board[i][col] = 0 # Backtrack
ld[i - col + N - 1] = rd[i + col] = cl[i] = 0
return False
def solve():
board = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
if (solveNQ(board, 0) == False):
print("No Solution exist")
return False
printSol(board)
return True
solve() Output:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0 Time Complexity: O(N * N!)
Space Complexity: O(N)
Conclusion
The N queen problem is a difficult one that can be solved with a backtracking algorithm. The problem necessitates careful consideration of the rules governing queen placement on a chessboard, and the backtracking algorithm provides an efficient method of searching for all possible solutions. The N queen problem has real-world applications in computer vision, where it can be used to solve problems like object recognition and tracking. As a result, knowing how to solve the N queen problem using backtracking is a valuable skill for any programmer.
FAQs(Frequently Asked Questions) on N Queen Problem
Here are some frequently asked questions (FAQs) and their answers on the N Queen problem:
Q1. What is the goal of the N Queen problem?
Ans: The goal of the N Queen problem is to find a configuration of the N queens on an NxN chessboard such that no two queens are attacking each other.
Q2. What is a valid solution to the N Queen problem?
Ans: A valid solution to the N Queen problem is a configuration of the N queens on an NxN chessboard such that no two queens are in the same row, column, or diagonal.
Q3. What is the brute force approach to solving the N Queen problem?
Ans: The brute force approach to solving the N Queen problem involves trying all possible combinations of placing the N queens on the chessboard and checking if each combination satisfies the constraints (i.e., no two queens are in the same row, column, or diagonal).
Q4. What is the backtracking approach to solving the N Queen problem?
Ans: The backtracking approach to solving the N Queen problem is a more efficient solution compared to the brute force approach. In this approach, we start by placing the first queen in the first row, then move to the next row and try to place the next queen, and so on. If we reach a point where it is not possible to place a queen, we backtrack and try a different position for the previous queen. We continue this process until we find a valid solution or all possibilities have been exhausted.
Q5. How can I solve the n-Queen problem?
Ans: There are several algorithms to solve the n-Queen problem, such as backtracking, genetic algorithms, and simulated annealing. The most common algorithm is backtracking, which involves trying to place queens on the board row by row, backtracking when a conflict is found, and continuing until a solution is found.
Q6. Can the n-Queen problem be solved for all values of n?
Ans: The n-Queen problem can be solved for all values of n, but the computational complexity of finding a solution increases rapidly as n increases. For large values of n, it may not be practical to find a solution using a brute-force algorithm.