Scribd
Upload
31 views

ai-pract4

The document outlines a solution for the n-queens problem using Branch and Bound and Backtracking methods, focusing on Constraint Satisfaction Problems (CSP). It explains the theory behind CSP, detailing its components and the specific constraints for the n-queens problem. The document also provides algorithms for solving the n-queens problem through Backtracking and Branch and Bound techniques, emphasizing the importance of efficiently tracking queen placements to avoid conflicts.

Uploaded by

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

ai-pract4

The document outlines a solution for the n-queens problem using Branch and Bound and Backtracking methods, focusing on Constraint Satisfaction Problems (CSP). It explains the theory behind CSP, detailing its components and the specific constraints for the n-queens problem. The document also provides algorithms for solving the n-queens problem through Backtracking and Branch and Bound techniques, emphasizing the importance of efficiently tracking queen placements to avoid conflicts.

Uploaded by

Nikita Khandare
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

TITLE: Implement a solution for a Constraint Satisfaction Problem using Branch and Bound and Backtracking for

n-queens problem or a graph coloring problem

AIM: To use Branch & Bound and Backtracking to solve CSP & n-queens or graph coloring problem.

OBJECTIVES: Based on above main aim following are the objectives

1. To study Branch & Bound and Backtracking methods.


2. To study Constraint Satisfaction Problem
3. To study n-queen or graph coloring problem

Theory:
Constraint Satisfaction Problems:
The objective of every problem-solving technique is one, i.e., to find a solution to reach the goal. Although,
in adversarial search and local search, there were no constraints on the agents while solving the problems and
reaching to its solutions. By the name, it is understood that constraint satisfaction means solving a problem under
certain constraints or rules.
Constraint satisfaction is a technique where a problem is solved when its values satisfy certain constraints
or rules of the problem. Such type of technique leads to a deeper understanding of the problem structure as well as
its complexity.
Constraint satisfaction depends on three components, namely:
X: It is a set of variables.
D: It is a set of domains where the variables reside. There is a specific domain for each variable. C: It is a set of
constraints which are followed by the set of variables.
In constraint satisfaction, domains are the spaces where the variables reside, following the problem specific
constraints. These are the three main elements of a constraint satisfaction technique. The constraint value consists of
a pair of {scope, rel}. The scope is a tuple of variables which participate in the constraint and rel is a relation which
includes a list of values which the variables can take to satisfy the constraints of the problem.

CSP Problems:
Constraint satisfaction includes those problems which contains some constraints while solving the problem. CSP includes the
following problems:
Graph Coloring: The problem where the constraint is that no adjacent sides can have the same color.
n-queen problem: In n-queen problem, the constraint is that no queen should be placed either diagonally, in the same row or
column. The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each
other.

Backtracking Algorithm to solve n-queen problem:


The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a
column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we
mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

1) Start in the leftmost column


2) If all queens are placed return true

3) Try all rows in the current column. Do following for

every tried row.

a) If the queen can be placed safely in this row then mark this [row,

column] as part of the solution and recursively check if placing


queen here leads to a solution.

b) If placing the queen in [row, column] leads to a solution then return


true.

c) If placing queen doesn't lead to a solution then unmark this [row,

column] (Backtrack) and go to step (a) to try other rows.


3) If all rows have been tried and nothing worked, return false to trigger
backtracking.

N Queen Problem using Branch and Bound:


In backtracking solution we backtrack when we hit a dead end. In Branch and Bound solution, after building a partial
solution, we figure out that there is no point going any deeper as we are going to hit a dead end.
“The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a
queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no
clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and
return false.”
1. For the 1st Queen, there are total 8 possibilities as we can place 1st Queen in any row of first column. Let’s
place Queen 1 on row 3.
2. After placing 1st Queen, there are 7 possibilities left for the 2nd Queen. But wait, we don’t really have 7
possibilities. We cannot place Queen 2 on rows 2, 3 or 4 as those cells are under attack from Queen 1. So,
Queen 2 has only 8 – 3 = 5 valid positions left.
3. After picking a position for Queen 2, Queen 3 has even fewer options as most of the cells in its column are
under attack from the first 2 Queens.
We need to figure out an efficient way of keeping track of which cells are under attack. In previous solution
we kept an 8--by--8 Boolean matrix and update it each time we placed a queen, but that required linear time to
update as we need to check for safe cells.
Basically, we have to ensure 4 things:

1. No two queens share a column.


2. No two queens share a row.
3. No two queens share a top-right to left-bottom diagonal.
4. No two queens share a top-left to bottom-right diagonal.

Number 1 is automatic because of the way we store the solution. For number 2, 3 and 4, we can perform
updates in O(1) time. The idea is to keep three Boolean arrays that tell us which rows and which diagonals are
occupied.
Let’s do some pre-processing first. Let’s create two N x N matrix one for / diagonal and other one for \
diagonal. Let’s call them slashCode and backslashCode respectively. The trick is to fill them in such a way that

two queens sharing a same /-diagonal will have the same value in
matrix slashCode, and if they share same \-diagonal, they will have the same value in
backslashCode matrix.
For an N x N matrix, fill slashCode and backslashCode matrix using below formula – slashCode[row]
[col] = row + col
backslashCode[row][col] = row – col + (N-1)

Using above formula will result in below matrices

The ‘N – 1’ in the backslash code is there to ensure that the codes are never negative because we
will be using the codes as indices in an array.
Now before we place queen i on row j, we first check whether row j is used (use an array to store
row info). Then we check whether slash code ( j + i ) or backslash code ( j – i + 7 ) are used (keep two
arrays that will tell us which diagonals are occupied). If yes, then we have to try a different location for
queen i. If not, then we mark the row and the two diagonals as used and recurse on queen i + 1. After the
recursive call returns and before we try another position for queen i, we need to reset the row, slash code
and backslash code as unused again
Conclusion: Thus we have studied how to solve n-queen (Constraint Satisfaction Problem) using
Backtracking and Branch & Bound

You might also like