[go: up one dir, main page]
Scribd
Upload
287 views12 pages

N Queen Problem

The document discusses the N-Queen problem, which involves placing N queens on an N x N chessboard such that no queen can attack any other. It can be solved using a brute force approach or backtracking. Backtracking involves trying all possible placements of queens row by row, and abandoning any partial configuration ("backtracking") as soon as a conflict is found. The document provides pseudocode for a backtracking algorithm to solve the N-Queens problem and find all solutions.

Uploaded by

Shrinath Tailor
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
287 views12 pages

N Queen Problem

The document discusses the N-Queen problem, which involves placing N queens on an N x N chessboard such that no queen can attack any other. It can be solved using a brute force approach or backtracking. Backtracking involves trying all possible placements of queens row by row, and abandoning any partial configuration ("backtracking") as soon as a conflict is found. The document provides pseudocode for a backtracking algorithm to solve the N-Queens problem and find all solutions.

Uploaded by

Shrinath Tailor
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
You are on page 1/ 12

THE N-QUEEN PROBLEM

Shrinath Tailor
Introduction
 N-Queens dates back to the 19th century (studied by Gauss)
 Classical combinatorial problem, widely used as a
benchmark because of its simple and regular structure
 Problem involves placing N queens on an N *N
chessboard such that no queen can attack any other
 Benchmark code versions include finding the first solution
and finding all solutions

Shrinath Tailor
The n-queen problem
 What is its input?
Ans. Positive integer n
 What is its task??
Ans. Place n queens on an n by n chessboard so that no two queens attack each
other (on same row, column, diagonal), or report that this is impossible.
 Solving particular problem for the different values of n=1,2,3,4.
 Pure brute force search
 16 squares on a 4 by 4 chessboard
 Leads to 16 * 15 * 14 * 13 = 43,680 possible solutions
Shrinath Tailor
For the larger values of n
 n=8
At most one queen per row: 88 = 16,777,216
Early backtracking: 2057 nodes total • Time to find
first solution: 114 nodes
 n=12
At most one queen per row: 1212
Early backtracking: 856,189 nodes total
Time to find first solution: 262 nodes
Shrinath Tailor
N-Queens Solutions
Various approaches to the problem •
 Brute force
 Local search algorithms
 Backtracking
 Divide and conquer approach
 Permutation generation
 Mathematical solutions
 Graph theory concepts
Shrinath Tailor
The backtracking method
 A given problem has a set of constraints and possibly an objective
function
 The solution optimizes an objective function, and/or is feasible.
 We can represent the solution space for the problem using a -
• The root of the tree represents 0 choices,
• Nodes at depth 1 represent first choice
• Nodes at depth 2 represent the second choice, etc.
• In this tree a path from a root to a leaf represents a
Shrinath Tailor

candidate solution
Solution of 4 – queen’s with the help of backtracking

The B denotes the dead node.

Shrinath Tailor
NQueens(k,n)
Algorithm
//Using backtracking,this procedure prints all possible
//placements of n queens on an n*n
//chessboard so that they are non attacking
{
for(i=1 to n ) do
{ if Place(k,i) then
{
x[k]=i;
If(k=n) then
write (x[1:n]);
else Nqueens(k+1,n);
}
Shrinath Tailor }
}
Algorithm

Algorithm Place(k,i)

For j=1 to k-1 do

if((x[j]=i) //same colum or (Abs(x[j]-i)=Abs(j-k)))//same diagonal then


return false;

Return true;

Shrinath Tailor
Thank you !!!

Shrinath Tailor
Shrinath Tailor
Shrinath Tailor

You might also like