III Year –I SEMESTER Design and Analysis of Algorithms

UNIT-V:
Backtracking: General method, 8-queen problem, sum of subsets problem, graph coloring,
Hamiltonian cycles, Knapsack problem.

Explain about General Method for backtracking.

Brute force approach is used in Greedy method and dynamic programming. Brute force
approach evaluates all possible solutions, among which, we select one solution as optimal
solution. In backtracking the problem will be solved in an efficient way when compared to
other techniques. This method we will use criterion function, implicit and explicit
constraints. This method was first introduced by H.J.Lehmer in 1950s.

Suppose mi is the size of set Si. Then there are m = m1m2,…mn, n-tuples that are possible
candidates for satisfying the function P. The brute force approach would be to form all
these n-tuples, evaluate each one with P and save those which yield the optimum. The
backtracking algorithm has an ability to yield the same answer with less than m trials. For
this it builds a solution vector one component at a time and to use modified criterion
function Pi(x1,…xn) to test whether the vector being formed has any chance of success.

Backtracking method requires that all the solutions satisfy a complex set of constrains. For
any problem these constraints are divided into two categories. They are;
 Explicit constraints depend on the particular instance I of the problem being solved.
All tuples that satisfy the explicit constraints define a possible solution space I.
 Implicit constraints are rules that determine which of the tuples in the solution space
I satisfies the criterion function.
Applications:
 N-Queens Problem
 Sum of Subsets Problem
 Graph Coloring Problem
 Hamiltonian Cycles
 Knapsack Problem

M. KOTESWARA RAO, ASST PROF, CSE, NIT 1|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Explain about n-Queen Problem.

The N queen problem is the problem of placing N chess queen on an NxN chessboard. So
that no two queens are on the same row, same column or diagonal. The solution space
consists of n! permutations of n-tuple.
Algorithm:
1. Place the queens column wise, start from the left most column
2. If all queens are placed.
1. Return true and print the solution matrix.
3. Else
1. Try all the rows in the current column.
2. Check if queen can be placed here safely if yes mark the current cell in solution
matrix as 1 and try to solve the rest of the problem recursively.
3. If placing the queen in above step leads to the solution return true.
4. If placing the queen in above step does not lead to the solution, BACKTRACK, mark
the current cell in solution matrix as 0 and return false.
4. If all the rows are tried and nothing worked, return false and print NO SOLUTION.

4 Queens Problem:
It consists of 4 queens that should be placed on a 4 x 4 chess board. So that no two queens
attack i.e. no two queens are on same row or same column or diagonal.
Algorithm: n-Queen problem Algorithm
 The First queen is placed in the first row and first column. So that the second queen
should not by on 1st row or 1s column or diagonal.

Q1 * * *
* *
*
*

 Q2 should not be placed in 1st row or 1st column or 2nd column of the 2nd row. To it
will be placed in 3rd column of the 2nd row.

M. KOTESWARA RAO, ASST PROF, CSE, NIT 2|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Q1 * * *
* * Q2 *
* * * *
* *

 We are unable to place Q3 in 3rd row so go back to Q2 and place it in 4th column.

Q1 * * * Q1 * * *
* * * Q2 * * * Q2
* * * * Q3 * *
* * * * * *

 We are unable to place Q4 in 4 th row because of diagonal attack from Q3, so go back
and remove Q3 and place it in the next column. But it is not possible, so move back
to Q2 and remove it to next column but it is not possible. So go back to Q1 and
move it to next column.

Q1 Q1
Q2

Q1 Q1
Q2 Q2
Q3 Q3
Q4

The solution to the 4- Queen’s problem is x1 = 2, x2 = 4, x3 = 1 and x4 =3. The state space
tree for the above problem is;

M. KOTESWARA RAO, ASST PROF, CSE, NIT 3|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Other possible Solutions:

x1 = 3, x2 = 1, x3 = 4 and x4 =2

8 Queen Problem:

It consists of 8 queens that should be placed on a 8 x 8 chess board. So that no two queens
attack i.e. no two queens are on same row or same column or diagonal.
Place (k, i) algorithm returns a Boolean value that is true if the k th queen is in ith column. Let
A[1:8, 1:8] chess board is represented as a 8x8 matrix. The queens are numbered 1 through
8.
Explicit Constraint: The explicit constraint specifies that 8 queens are to be placed in 8 x 8
chess board in 88 ways. The solution space is reduced by applying implicit constraints.
Implicit Constraint: Implicit constraints specify that no two queens are in the same row, or
column or diagonal.

M. KOTESWARA RAO, ASST PROF, CSE, NIT 4|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Suppose two queens are placed at positions (i, j) and (k, l) then they are on the same
diagonal if and only if |j - l| = | i - k|.
Time Complexity: O(8!)
Algorithm:
Algorithm Place (k,i)

for j :=1 to k-1 do

if (x[i] – i) or abs(x[j]-i) = abs(k-k)) then

return false;

Algorithm NQueens(k,n)

for i := 1 to n do

if Place (k,i) then

x[k] : = i;

if (k = n) then write (x[1:n]);

else

NQueent(k+1, n);

M. KOTESWARA RAO, ASST PROF, CSE, NIT 5|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Possible Solutions:

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

1. (x1, x2, x3, x4, x5, x6, x7, x8) = (3, 6, 2, 7, 1, 4, 8, 5)

2. (x1, x2, x3, x4, x5, x6, x7, x8) = (4, 6, 8, 2, 7, 1, 3, 5)
3. (x1, x2, x3, x4, x5, x6, x7, x8) = (4, 7, 3, 8, 2, 5, 1, 6)
4. (x1, x2, x3, x4, x5, x6, x7, x8) = (5, 2, 4, 7, 3, 8, 6, 1)
5. (x1, x2, x3, x4, x5, x6, x7, x8) = (4, 2, 7, 3, 6, 8, 5, 1)
6. (x1, x2, x3, x4, x5, x6, x7, x8) = (4, 6, 8, 3, 1, 7, 5, 2)
7. (x1, x2, x3, x4, x5, x6, x7, x8) = (3, 6, 8, 1, 4, 7, 5, 2)
8. (x1, x2, x3, x4, x5, x6, x7, x8) = (5, 3, 8, 4, 7, 1, 6, 2)
9. (x1, x2, x3, x4, x5, x6, x7, x8) = (5, 7, 7, 1, 3, 8, 6, 2)
10. (x1, x2, x3, x4, x5, x6, x7, x8) = (4, 1, 5, 8, 6, 3, 7, 2)
11. (x1, x2, x3, x4, x5, x6, x7, x8) = (3, 6, 4, 1, 8, 5, 7, 2)
12. (x1, x2, x3, x4, x5, x6, x7, x8) = (6, 2, 7, 1, 4, 8, 5, 3)
13. (x1, x2, x3, x4, x5, x6, x7, x8) = (4, 7, 1, 8, 5, 2, 6, 3)
14. (x1, x2, x3, x4, x5, x6, x7, x8) =(6, 4, 7, 1, 8, 2, 5, 3)
15. (x1, x2, x3, x4, x5, x6, x7, x8) = (3, 5, 2, 8, 1, 7, 4, 6)

M. KOTESWARA RAO, ASST PROF, CSE, NIT 6|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Describe the 4-queens problem using backtracking

4 Queens Problem sub heading in the above question.
Briefly explain 8-queen problem using backtracking. Explain its application
(OR)
Write an algorithm for how Eight Queen’s problem can be solved using back tracking and
explain with an example.
(OR)
Suggest a solution for 8 queen’s problem.
8 Queens Problem sub heading in the above question.

Write a recursive backtracking algorithm for sum of subsets problem

(OR)
Explain in detail about sum of subsets problem.

The sum of subsets problem is to find a subset of given set S= ,S1, S2, ….., Sn- of ‘n’ positive
integers whose sum of elements is equal to a given positive integer ‘m’.
Recursive algorithm for sum of subsets:
Algorithm SumOfSub(s, k, r)
// Find all subsets of w[1:n] that sum to m. The values of x[j], 1<=j<=k, have already been
determined. The w[j] is in non decreasing order.
{
x[k]:=1;
if (s+w[k] = m) then write (x[1:k]);
if((s+r-w[k]>=m) and (s+w[k+1]<=m) then
{
x[k] := 0;
SumOfSub(s, k+1, r-w[k]);
}
}

M. KOTESWARA RAO, ASST PROF, CSE, NIT 7|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Ex:
S={1, 2, 5, 6, 8}
Find a subset of set S where sum of elements is 9.
Subset - Sum
{1} - 1
{1, 2} - 3
{1, 2, 5} - 8
{1, 2, 5, 6} - 14 Sum exceeds 9 hence back track
{1, 2, 6} - 9

State Space Tree: It will be drawn just like a binary tree.

1. The root node is set to 0. Because initially no elements are added to the subset.
2. Arrange the elements in increasing order.
1, 2, 5, 6, 8
3. Check the sum of sub set at each time by including the element or excluding the
element. If the element is included then go to left. Otherwise go to right.
4. If the sum > given sum then stop adding and backtrack. Continue this process until
the solution is found.

M. KOTESWARA RAO, ASST PROF, CSE, NIT 8|P age

III Year –I SEMESTER Design and Analysis of Algorithms

Exercise:
1. Consider a set S= {5, 10, 12, 13, 15, 18} and d= 30. Solve it for obtaining sum of
subset.
2. {5, 7, 10, 12, 15, 18, 20} and m= 35.
3. {3, 2, 7, 1} and m=6.
4. {2, 4, 6, 8, 10} and m=20.
5. {7, 11, 13, 24} and m = 31

Briefly explain graph coloring using backtracking.

(OR)
Describe Backtracking technique to m-coloring graph. Explain with example
(OR)
What is Graph coloring? Write an algorithm for it and explain with an example
(OR)
Explain about graph coloring and chromatic number.
Let G be a graph and m be a given positive integer. Graph coloring is a problem of coloring
the nodes of graph G in such a way no two adjacent nodes have the same color yet only m
colors are used. ‘d’ is the degree of the graph then d+1 colors are used to color a graph.
According to m-colorability optimization the smallest integer ‘m’ can be used for coloring a
graph G.
Chromatic Number of a graph defines the number of colors that are used in coloring a
graph.
Algorithm mColoring (k)
/* This algorithm was formed using the recursive backtracking schema. The graph is
represented by its Boolean adjacency matrix G*1:n, 1:n+. all assignments of 1, 2, 3, …., m to
the vertices of the graph such that adjacent vertices assigned distinct integers are print3d. k
is the index of the next vertex to color.*/
{
repeat
{
NextValue(k);

M. KOTESWARA RAO, ASST PROF, CSE, NIT 9|P age

III Year –I SEMESTER Design and Analysis of Algorithms

if (x[k]=0) then return;

if (k=n) then
write (s[i:n]);
else mColoring(k+1);
} until (false);
}
Algorithm NextValue(k)
{
repeat
{
x[k]:= (x[k]+1) mod (m+1);
if (x[k]=0) then return;
for j:=1 to n do
{
if ((G[k,j] #0 ) and (x[k] = x[j])) then
break;
}
If (j=n+1) then return;
} until (false);
}

Time Complexity : O(n.mn)

State Space Tree for Graph-Coloring when n=3 and m=3

M. KOTESWARA RAO, ASST PROF, CSE, NIT 10 | P a g e

III Year –I SEMESTER Design and Analysis of Algorithms

Ex:

There are 6 solutions to the 3-Coloing problem.

Solutions
Node
I II III IV V VI
1 1 1 2 2 3 3
2 2 3 1 3 2 1
3 3 2 3 1 1 2
4 2 3 1 3 2 1

Exercise:
Draw the search tree to color the graph with the three colors: red, blue, green.

M. KOTESWARA RAO, ASST PROF, CSE, NIT 11 | P a g e

III Year –I SEMESTER Design and Analysis of Algorithms

Briefly explain Hamiltonian cycles using backtracking.

(OR)
What is Hamiltonian Cycle? Describe with an example.
(OR)
Explain how the Hamiltonian circuit problem is solved by using the backtracking concept.
A graph can be visualized as a collection of points or vertices connected by lines or edges. A
cycle is a walk along a path of edges visiting vertices until ending at the originating vertex. A
Hamiltonian cycle is a cycle that visits every vertex in a graph exactly once except the
starting vertex. When the number of vertices is increased, it is difficult to find out the
Hamiltonian cycle. A graph possessing a Hamiltonian circuit is said to be a Hamiltonian
Graph.
Ex:

In the above figure G1 contains two Hamiltonian Cycles i.e. 1, 2, 8, 7, 6, 5, 4, 3, 1 and 1, 3, 4,

5, 6, 7, 8, 2, 1, and G2 contains no Hamiltonian Cycles.

The backtracking method given a solution to find out the Hamiltonian Cycles.

1. The solution vector X(x1, ……,xn) is defined so that xi represents the ith visited vertex
of the proposed cycle.

M. KOTESWARA RAO, ASST PROF, CSE, NIT 12 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

2. Now all we need do is to determine how to compute the set of possible vertices for
xk if x1, …., xk-1 have already been chosen.
3. If k=1 then x1 can be any of the n vertices. To avoid the printing of same cycle n
times, we require that x1 = 1. If 1<k<n, then x1 can be any vertex v that is distinct
from x1, x2, …. xk-1 and v is connected by an edge to xk-1.
4. The vertex xn can only be the remaining vertex need to be connected to both xn-1 and
x1.
5. NextValue function is a recursive backtracking schema to find all the Hamiltonian
Cycles. This algorithm is started by initializing the adjacency matrix G[1:n, 1:n], then
setting x[2 : n] to zero and x[i1] to 1 and then executing Hamiltonian(2).

Example:
Consider a graph G = (V, E) shown in fig. we have to find a Hamiltonian circuit using Backtracking
method.

Solution: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our implicit tree.

Next, we choose vertex 'b' adjacent to 'a' as it comes first in lexicographical order (b, c, d).

M. KOTESWARA RAO, ASST PROF, CSE, NIT 13 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

Next, we select 'c' adjacent to 'b.'

Next, we select 'd' adjacent to 'c.'

Next, we select 'e' adjacent to 'd.'

M. KOTESWARA RAO, ASST PROF, CSE, NIT 14 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

Next, we select vertex 'f' adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have already
visited. Thus, we get the dead end, and we backtrack one step and remove the vertex 'f' from partial
solution.

From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already been
checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex adjacent to d
are e, f from which e has already been checked, and adjacent of 'f' are d and e. If 'e' vertex, revisited
them we get a dead state. So again we backtrack one step.

Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a.' Here,
we get the Hamiltonian Cycle as all the vertex other than the start vertex 'a' is visited only once. (a - b - c
- e - f -d - a).

M. KOTESWARA RAO, ASST PROF, CSE, NIT 15 | P a g e

III Year –I SEMESTER Design and Analysis of Algorithms

M. KOTESWARA RAO, ASST PROF, CSE, NIT 16 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

Again Backtrack

Here we have generated one Hamiltonian circuit, but another Hamiltonian circuit can also be obtained
by considering another vertex.

Exercise:

M. KOTESWARA RAO, ASST PROF, CSE, NIT 17 | P a g e

III Year –I SEMESTER Design and Analysis of Algorithms

Algorithm:
Algorithm Hamiltonian (k)
/* This algorithm uses the recursive formulation of backtracking to find all the Hamiltonian
Cycles of a graph. the graph is stored as an adjacency matrix G[1 : n, 1 : n]. All cycles begin
at node 1.
{
repeat
{
NextValue(k);
if ( x[k] = 0 ) then return;
if ( k = n ) then write (x[1 : n]);
else Hamiltonian ( k+1);
} until (false);
}
Algorithm NextValue(k)
{
repeat
{
x[k] = (x[k]) +1) mod (n+1);
if (x[k]=0) then return;
if (G[x[k-1], x[k] # 0) then
{
for j:= 1 to k-1 do if (x[j] = x[k]) then break;
if (j=k) then
if ( (k<n) pr ((k = n) and G[x[n], x[1] #0)) then return;
}
}until (false);
}

M. KOTESWARA RAO, ASST PROF, CSE, NIT 18 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

1. Write an algorithm for how Knapsack problem can be solved using backtracking and
explain with an example.
2. Solve the Knapsack problem by using backtracking and explain with an example?

Knapsack Problem using Backtracking can be solved as follow:

The knapsack problem is useful in solving resource allocation problems.

Let X = <x1, x2, x3, . . . . . , xn> be the set of n items,
W = <w1, w2, w3, . . . , wn> and V = <v1, v2, v3, . . . , vn> be the set of weight and value
associated with each item in X, respectively.
Let M be the total capacity of the knapsack, i.e. knapsack cannot hold items having a
collective weight greater than M.
Select items from X such that it maximizes the profit and the collective weight of selected
items does not exceed the knapsack capacity.
The knapsack problem has two variants. 0/1 knapsack does not allow breaking up the item,
whereas a fractional knapsack does. 0/1 knapsack is also known as a binary knapsack.
The Knapsack problem can be formulated as,
Algorithm:

Algorithm Knapsack(xiwi, xipi)

{
xi=1;
I if(xiwi==m)
Then write (1:n, xipi )
I if(xiwi<m)
knapsack(xiwi+ wi+1, xipi+pi+1)
I if(xiwi>m)
xi=0;
knapsack(xiwi, xipi)
}

M. KOTESWARA RAO, ASST PROF, CSE, NIT 19 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

Example: Consider knapsack problem : n = 8. (W , W , W , W , W , W , W , W ) = (1, 11, 21, 23,

1 2 3 4 5 6 2 8

33, 43, 45, 55), P = (11, 21, 31, 33, 43, 53, 55, 65), m = 110. Solve the problem using
backtracking approach.

Solution:

Here M = 110 and n = 8.

Initially, cp = cw = 0, fp = – 1, k = 0

For k = 1:

cp = cp + p1 = 0 + 11 = 11

cw = cw + w1 = 0 + 1 = 1

cw < M, so select item 1

k = k+1=2

M. KOTESWARA RAO, ASST PROF, CSE, NIT 20 | P a g e

III Year –I SEMESTER Design and Analysis of Algorithms

For k=1:

cp = cp + p2 = 11 + 21 = 32

cw = cw + w2 = 1 + 11 = 12

cw < M, so select item 2

k = k+1=2

For k = 2:

cp = cp + p3 = 32 + 31 = 63

cw = cw + w3 = 12 + 21 = 33

cw < M, so select item 3

k = k+1=3

For k = 3:

cp = cp + p4 = 63 + 33 = 96

cw = cw + w4 = 33 + 23 = 56

cw < M, so select item 4

k = k+1=4

For k = 4:

cp = cp + p5 = 96 + 43 = 139

cw = cw + w5 = 56 + 33 = 89

cw < M, so select item 5

k = k+1=5

M. KOTESWARA RAO, ASST PROF, CSE, NIT 21 | P a g e

 III Year –I SEMESTER Design and Analysis of Algorithms

For k = 5:

cp = cp + p6 = 139 + 53 = 192

cw = cw + w6 = 89 + 43 = 132

cw > M, so reject item 6 and find upper bound

cp = cp – p6 = 192 – 53 = 139

cw = cw – w6 = 132 – 43 = 89

ub = cp + ((M – cw ) / w i+1) * pi+1

b = cp + [(110 – 89) / 43] * 53 = 164.88

Inclusion of any item from {I6, I7, I8} will exceed the capacity. So let’s backtrack to item 4.

The space tree would look like as shown in Fig. P. 6.7.2.

Upper bound at node 1:

ub = cp + ((M – cw ) / w i+1) * pi+1

= 139 + [(110 – 89)] / 43 * 53 = 164.88

Upper bound at node 2:

= 96 + [(110 – 56) / 33] * 43 = 166.09

Upper bound at node 3:

= 63 + [(110 – 33) / 33] * 43 = 163.33

M. KOTESWARA RAO, ASST PROF, CSE, NIT 22 | P a g e

III Year –I SEMESTER Design and Analysis of Algorithms

Compare and contrast between Brute force approach and Backtracking.

"Brute force" is a problem solving strategy by which you first generate a superset of all
candidate sequences for the solution and then filter out the elements of this set one-by-
one, resulting in a final set of solutions.

"Backtracking" is a method used to generate the superset used in brute force technique. It
generates sequences without repetition and based on an ordering of possible values of
sequence entities.

IMPORTANT QUESTIONS
1. Explain about General Method for backtracking.
2. Write an algorithm for how Eight Queen’s problem can be solved using back
tracking and explain with an example.
3. (A) Write a recursive backtracking algorithm for sum of subsets problem
(B) The set S={1, 2, 5, 6, 8}. Find a subset of set S where sum of elements is 9. And
also draw the state space tree.
4. (A) Describe Backtracking technique to m-coloring graph. Explain with example.
(B) Draw the state space tree for graph coloring when n=3 and m=3.
5. Explain how the Hamiltonian circuit problem is solved by using the backtracking
concept. Explain it with an example.

6. Solve the Knapsack problem by using backtracking and explain with an example?

M. KOTESWARA RAO, ASST PROF, CSE, NIT 23 | P a g e