Laboratory Practice II T.E. Computer Assignment No.

Assignment No. :04 Date:

Title : Implement a solution for a Constraint Satisfaction Problem

using Branch and Bound and Backtracking for n-queens problem or a graph coloring
problem.
Performance & Innovation Timely Total Sign & Date
Understanding Completion
3 1 1 5

Problem Definition: Implement a solution for a Constraint Satisfaction Problem

using Branch and Bound & Backtracking for n-queens problem.

Input: no of rows for the square Board

Output: All queens are placed at its proper position

Theory:
Constraint Satisfaction Problem
CSP depends on three Components
X: It is a set of variables
D: It is a set of domains where the variables are side There is a specific domain for each variable.
C: It is a set of constraints which are followed by the sets e to f variables.
Backtracking Algorithm
Backtracking is an algorithmic-technique for solving problems recursively by trying to build a
solution incrementally, one piece at a time, removing those solutions that fail to satisfy the
constraints of the problem at any point of time (by time, here, is referred to the time elapsed till
reaching any level of the search tree).
Branch and Bound
Branch and bound is an algorithm design paradigm which is generally used for solving
combinatorial optimization problems. These problems are typically exponential in terms of
time complexity and may require exploring all possible permutations in the worst case. The
Branch and Bound Algorithm technique solves these problems relatively quickly.
The branch and bound solution is somehow different, it generates a partial solution until
Department of Computer Engineering MCERC, Nashik 422105 1
Laboratory Practice II T.E. Computer Assignment No.4

itfiguresthatthere'snopointgoingdeeperaswewouldultimatelyleadtoadeadend.
In the backtracking approach, we maintain an 8x8 binary matrix for keeping track of safe
cells (by eliminating the unsafe cells, those that are likely to be attacked) and update it each
time we place a new queen. However, it required O(n^2) time to check the safe cell and
update the queen.
Applying the branch and bound approach: The branch and bound approach suggests that
we create a partial solution and use it to ascertain whether we need to continue in a particular
direction or not.
N-Queens problem
The N-Queens problem is a puzzle of placing exactly N queens on an NxN chessboard, such
that no two queens can attack each other in that configuration. Thus, no two queens can lie in
the same row, column or diagonal.
The idea is to place queens one by one in different columns, starting from the left most
columns. 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.
In a 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.”

 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.

Department of Computer Engineering MCERC, Nashik 422105 2

 Laboratory Practice II T.E. Computer Assignment No.4

 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.
 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.
 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 backslash Code 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 slash Code and back slash Code 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
Department of Computer Engineering MCERC, Nashik 422105 3
 Laboratory Practice II T.E. Computer Assignment No.4

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:

In This way we have studied how to solve the CSP problem and how to place 8 queens on board
with non-attacking mode using backtracking.

Exercise:
1. Difference between Backtracking and Branch-N-Bound technique
2. Calculate the time complexity for N queen algorithm using backtracking.

Department of Computer Engineering MCERC, Nashik 422105 4