N–Queen Problem in DAA

Learn the N–Queen Problem in DAA using the Backtracking method. Understand the algorithm, isSafe condition, 4-Queen example, time complexity O(N!), space complexity, advantages, and limitations.

Introduction

The N–Queen Problem is a classic Backtracking problem.
In this problem, N queens are placed on an N × N chessboard in such a way that no queen can attack any other queen.

When Does a Queen Attack Another Queen?

A queen can attack another queen if it is placed:

In the same row
In the same column
On the same diagonal

Objective of the Problem

Exactly one queen in each row
Exactly one queen in each column
No two queens should be placed on the same diagonal

N–Queen Problem Using Backtracking

Queens are placed row by row
For each row, all columns are checked
If a queen cannot be placed safely, the algorithm backtracks and tries another position

Checking Safe Position (isSafe)

To check whether a queen can be placed safely at a given position:

Check if there is another queen in the same column
Check the upper left diagonal
Check the upper right diagonal

(There is no need to check the row, since only one queen is placed per row.)

N–Queen Algorithm (Backtracking)

NQueen(row)
{
if (row == N)
print the solution
else
for col = 1 to N
{
if (isSafe(row, col))
{
board[row][col] = 1
NQueen(row + 1)
board[row][col] = 0 // Backtrack
}
}
}

N-Q Ex

Time Complexity

Worst Case Time Complexity: O(N!)
This is because all possible arrangements of queens may need to be checked

Space Complexity

O(N²) – for storing the chessboard
O(N) – for the recursive call stack

Advantages of the N–Queen Problem

A very good example to understand the Backtracking technique
Useful for studying Constraint Satisfaction Problems
Enhances algorithmic and logical thinking

Limitations of the N–Queen Problem

Requires a large amount of time for large values of N
Exponential time complexity makes it impractical for very large inputs

Conclusion

The N–Queen Problem clearly illustrates both the strengths and limitations of the Backtracking method.
It is an important problem in the Limitations of Algorithmic Power unit and is widely used to explain complex problem-solving techniques.

Some More:

N–Queen Problem in DAA