Scribd
Upload
13 views7 pages

N-Queens Problem: Backtracking Method

The N-Queens Problem involves placing N queens on an N×N chessboard such that no two queens can attack each other, adhering to specific rules regarding their placement. The backtracking algorithm is employed to find valid arrangements by recursively placing queens and backtracking when necessary. This problem has applications in AI, resource allocation, VLSI design, and algorithm testing, but it can be computationally expensive for larger values of N.

Uploaded by

sukkavigneshgoud977
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
13 views7 pages

N-Queens Problem: Backtracking Method

The N-Queens Problem involves placing N queens on an N×N chessboard such that no two queens can attack each other, adhering to specific rules regarding their placement. The backtracking algorithm is employed to find valid arrangements by recursively placing queens and backtracking when necessary. This problem has applications in AI, resource allocation, VLSI design, and algorithm testing, but it can be computationally expensive for larger values of N.

Uploaded by

sukkavigneshgoud977
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

N-Queens Problem –

Backtracking Approach

Presented By:
K. Charan Raju 23N81A6650
Problem Statement & Rules
Problem Statement:
Place N queens on an N×N chessboard so that no two queens
attack each other.

Rules & Constraints:


•A queen can move any number of squares: horizontally,
vertically, diagonally.
•No two queens can be in the same:
• Row
• Column
• Diagonal
•Originally for 8 queens (8×8 board), now generalized to any N×N
board.
This problemFind
•Objective: wasall
first proposed
valid by Max Bezzel
arrangements in 1848,
satisfying focusing
these rules. on 8
queens. It was later generalised to N queens on an N×N board.
Algorithm & Steps

Algorithm: Backtracking

Steps:
1. Start at the first row.
2. Place a queen in the first safe column.
3. Move to the next row.
4. If no safe column, backtrack to the previous row
and move the queen.
5. Continue until all queens are placed or all
possibilities are tried.
Example (N=4)
•Step 1: Place queen at (0, 1).

•Step 2: Place queen at (1, 3).

•Step 3: Place queen at (2, 0).

•Step 4: Place queen at (3, 2) → Valid solution.

•Backtrack when stuck and try different positions.

•Total Solutions for N=4: 2 unique


configurations.
Applications

AI & Constraint Satisfaction Resource Allocation & Scheduling


Fundamental for solving complex problems where Optimising assignment of resources (e.g., classrooms,
choices limit future options, like Sudoku solvers or logic employees) to tasks without conflicts.
puzzles.

VLSI Design Algorithm Testing


Used in placing components on integrated circuits to Used for evaluating the performance and correctness of
minimise interference and maximise efficiency. new search or optimisation algorithms.
Advantages, Disadvantages
Advantages Disadvantages
• Clear illustration of recursion and backtracking principles. • Computationally expensive for large N, due to its
• Excellent practice problem for coding interviews, factorial time complexity.
testing logical thinking and problem-solving skills. • Requires careful implementation to manage the
• Applicable to a wide range of real-world constraint state and backtrack correctly.
problems. • Can lead to stack overflow for very deep recursion
without proper tail call optimization (if supported).
Thank
You

You might also like