FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

N-Queen Problem



Introduction

The N-Queen Problem is one of the most popular applications of the Backtracking technique. The objective is to place N queens on an N × N chessboard such that no two queens attack each other.

A queen can attack another queen if they are placed in the same row, column or diagonal. Therefore, the algorithm must place queens carefully while satisfying all these constraints.

Problem Statement

Place N queens on an N × N chessboard so that no two queens share the same row, column or diagonal.

Why Backtracking?

Whenever a queen is placed in an invalid position, the algorithm immediately removes it and tries another position. This "undo" operation is called Backtracking.

Rules of the N-Queen Problem

Rule Description
Same Row No two queens can be placed in the same row.
Same Column No two queens can be placed in the same column.
Main Diagonal No two queens can attack each other diagonally.
Secondary Diagonal Queens cannot share the opposite diagonal.

Chessboard Illustration


      1   2   3   4

1     Q   -   -   -

2     -   -   Q   -

3     -   -   -   -

4     -   Q   -   -

Figure 1 : Partial Placement of Queens

Real-Life Example

Suppose four CCTV cameras are to be installed in a square hall. Each camera covers its entire row, column and both diagonals. The objective is to position the cameras so that no camera overlaps the coverage area of another camera. This is similar to the N-Queen Problem.

Solved Example (4-Queen Problem)

Consider a 4 × 4 chessboard. The algorithm places one queen in each row while checking whether the placement is safe.

Row Selected Column Status
1 2 Safe
2 4 Safe
3 1 Safe
4 3 Safe (Solution Found)

Final Solution


      1   2   3   4

1     -   Q   -   -

2     -   -   -   Q

3     Q   -   -   -

4     -   -   Q   -

Figure 2 : One Valid Solution of the 4-Queen Problem

State Space Tree

The Backtracking algorithm explores possible queen placements using a State Space Tree. 


               Row 1

          /   |   |   \

         C1  C2  C3  C4

              |

            Row 2

          Safe Positions

              |

            Row 3

              |

            Row 4

              |

         Solution Found

Figure 3 : State Space Tree of the N-Queen Problem

N-Queen Algorithm

NQueen(Row) Step 1 : If all queens are placed, Display the solution and return. Step 2 : For every column in the current row Step 3 : Check whether placing the queen is safe. Step 4 : If safe, Place the queen. Step 5 : Recursively place the queen in the next row. Step 6 : If no solution is found, Remove the queen (Backtrack). Step 7 : Try the next column.

Dry Run of the Algorithm

The following steps illustrate the execution of the algorithm for the 4-Queen Problem.

Step Action Result
1 Place Queen in Row 1, Column 2. Safe
2 Place Queen in Row 2, Column 4. Safe
3 Try Queen in Row 3, Column 2. Rejected
4 Place Queen in Row 3, Column 1. Safe
5 Place Queen in Row 4, Column 3. Solution Found

Complexity Analysis

Parameter Complexity Remarks
Best Case O(N) Rare case where valid positions are found immediately.
Average Case Problem Dependent Depends on pruning efficiency.
Worst Case O(N!) Many invalid combinations are explored.
Space Complexity O(N) Recursive call stack.

Advantages of the N-Queen Algorithm

  • Produces an exact solution whenever one exists.
  • Uses pruning to eliminate invalid placements.
  • Demonstrates the power of Backtracking.
  • Simple recursive implementation.
  • Applicable to many constraint satisfaction problems.

Limitations of the N-Queen Algorithm

  • Worst-case time complexity is factorial.
  • Execution time increases rapidly with larger values of N.
  • Requires recursive function calls.
  • Not suitable for very large chessboards without optimization.

Applications of the N-Queen Problem

Application Description
Artificial Intelligence Constraint satisfaction problems.
Scheduling Conflict-free assignment of tasks.
VLSI Design Component placement optimization.
Robotics Search and planning algorithms.
Game Development State space search problems.

N-Queen Problem vs Graph Coloring

N-Queen Problem Graph Coloring
Places queens on a chessboard. Assigns colours to graph vertices.
Constraint: Rows, Columns and Diagonals. Constraint: Adjacent vertices cannot have the same colour.
Uses a chessboard representation. Uses graph representation.
Solved using Backtracking. Solved using Backtracking.

💡 Remember This

One Queen Per Row

One Queen Per Column

No Two Queens on the Same Diagonal

Always check these three conditions before placing a queen.

Important Points

  • The N-Queen Problem is a classical Backtracking problem.
  • Only one queen is placed in each row.
  • Each placement is checked for safety.
  • If a placement is invalid, the algorithm backtracks.
  • The algorithm uses a State Space Tree for searching.
  • Worst-case time complexity is O(N!).

💼 Interview Corner

  • Why is the N-Queen Problem solved using Backtracking?
  • What conditions must be checked before placing a queen?
  • Why is the worst-case complexity O(N!)?
  • What is the purpose of the State Space Tree?
  • Can the N-Queen Problem be solved using Dynamic Programming?

🎓 AKTU Examination Tip

AKTU examinations frequently ask students to solve the 4-Queen Problem, draw the State Space Tree, write the Backtracking algorithm and explain the safety conditions used while placing a queen.

Summary

The N-Queen Problem is a classical application of the Backtracking technique. It places queens one row at a time while checking row, column and diagonal constraints. Whenever an invalid position is encountered, the algorithm backtracks and tries another position. Although the worst-case complexity is O(N!), Backtracking significantly reduces the search space by pruning invalid branches.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com