Name:
Krishna Dubey
Enrollment No:
0205AL231029
Subject:
Analysis and Design Algorithm
Topic:
N Queen Problems
N-Queen
Problem
A Backtracking Approach to
Solving the N-Queens
Challenge
Introduction
The N-Queen Problem is a well-known puzzle that
involves placing N queens on an N×N chessboard such
that no two queens threaten each other. This
presentation explores the problem statement,
constraints, and examples of the N-Queen solution,
primarily focusing on the 8-Queen variant.
Definition of
Backtracking
Backtracking is a systematic method for solving problems
incrementally by trying partial solutions and then removing those
that fail to satisfy the conditions of the problem. It is often used for
optimization problems and allows for exploring various possible
configurations until a solution is found or all possibilities are
exhausted.
Problem Statement
The core objective of the N-Queen Problem is to position N
queens on an N×N chessboard so that no two queens can
attack each other. This means that no two queens may share
the same row, column, or diagonal. The challenge becomes
exponentially more complex as N increases.
Constraints
-To solve the N-Queen Problem, several
constraints must be adhered to.
-First, each queen must occupy a different
row and column.
-Additionally, the queens must be placed
in such a manner that they do not share
any diagonals, which would allow them to
attack one another.
-These constraints are critical for
achieving a valid configuration.
Example (8-
Queen)
The 8-Queen Problem is a specific case of
the N-Queen Problem where N is equal to
8. A successful configuration requires
placing 8 queens on an 8×8 chessboard,
ensuring that no two queens threaten
each other. There are 92 different
arrangements, of which 12 are unique
when accounting for board rotations and
reflections.
Solving the 8-Queen Problem
-Chessboard: 8 rows × 8 columns.
-Total Solutions: 92 (but 12 unique
considering rotations).
-Sample Solution:
Queen Positions:((1,5),(2,7),
(3,1),
(4,3),(5,8),(6,6),(7,4),(8,2))
Algorithm
isValid(board, row, col)
Input: The chess board, row and the column of the
board.
Output - True when placing a queen in row and
place position is a valid or not.
Begin
if there is a queen at the left of current col, then
return false
if there is a queen at the left upper diagonal, then
return false
if there is a queen at the left lower diagonal, then
return false;
End
Time and Space
Complexity
• Time Complexity: O(N!) (Worst-case,
explores all permutations).
• Space Complexity: O(N) (For storing
queen positions).
Applications
of N-Queen
Problem
• Used in puzzle games,
AI, and constraint
satisfaction problems.
• Helps
understand recursion,
backtracking, and
problem-solving
strategies.
Conclusions
• The N-Queen problem is a classic example
of backtracking.
• The 8-Queen problem has 92 solutions, but
only 12 unique ones.
• Can be extended to N×N chessboards with
the same logic.
THANK YOU
"This presentation is dedicated to all the
queens who didn't attack each other. You're an
inspiration to us all. And to everyone else,
thanks for listening!"