DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

DAA 6TH UNIT DETAILS

UNIT VI:
Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph
coloring, Hamiltonian cycles.

Important Questions for exam point of view:

1. (a) Explain, how the Hamiltonian circuit problem is solved by using the
BACKTRACKING concept.
(b) Device a backtracking algorithm for m-coloring graph problem.

2. (a) Compare and contrast between Brute force approaches Vs Backtracking.

(b) Suggest a solution for 8 queen’s problem.

3. (a) Explain about graph coloring and chromatic number.

(b) For the graph given below, draw the portion of the state space tree generated by
procedure MCOLORING.

4. (a) Compare and contrast between Brute force approach and Backtracking.
(b) Find the Hamiltonian circuit in the following graph by using backtracking.

bphanikrishna.wordpress.com 1 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

bphanikrishna.wordpress.com 2 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

UNIT-VI

Backtracking (General method)

Many problems are difficult to solve algorithmically. Backtracking makes it possible to solve
at least some large instances of difficult combinatorial problems.

Suppose you have to make a series of decisions among various choices, where

 You don’t have enough information to know what to choose

 Each decision leads to a new set of choices.
 Some sequence of choices ( more than one choices) may be a solution to your
problem.

Backtracking is a methodical (Logical) way of trying out various sequences of decisions,

until you find one that “works”

Example@1 (net example) : Maze (a tour puzzle)

Given a maze, find a path from start to finish.

 In maze, at each intersection, you have to decide between 3 or fewer choices:

 Go straight
 Go left
 Go right
 You don’t have enough information to choose correctly
 Each choice leads to another set of choices.
 One or more sequences of choices may or may not lead to a solution.
 Many types of maze problem can be solved with backtracking.

Example@ 2 (text book):

Sorting the array of integers in a[1:n] is a problem whose solution is expressible by an n-tuple

xi is the index in ‘a’ of the ith smallest element.

The criterion function ‘P’ is the inequality a[xi]≤ a[xi+1] for 1≤ i ≤ n

bphanikrishna.wordpress.com 3 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Si is finite and includes the integers 1 through n.

misize of set Si

m=m1m2m3---mn n tuples that possible candidates for satisfying the function P.

With brute force approach would be to form all these n-tuples, evaluate (judge) each one with
P and save those which yield the optimum.

By using backtrack algorithm; yield the same answer with far fewer than ‘m’ trails.

Many of the problems we solve using backtracking requires that all the solutions satisfy a
complex set of constraints.

For any problem these constraints can be divided into two categories:

 Explicit constraints.
 Implicit constraints.

Explicit constraints: Explicit constraints are rules that restrict each xi to take on values only
from a given set.

Example: xi ≥ 0 or si={all non negative real numbers}

Xi=0 or 1 or Si={0, 1}

li ≤ xi ≤ ui or si={a: li ≤ a ≤ ui }
The explicit constraint depends on the particular instance I of the problem being solved. All
tuples that satisfy the explicit constraints define a possible solution space for I.

Implicit Constraints:

The implicit constraints are rules that determine which of the tuples in the solution space of I
satisfy the criterion function. Thus implicit constraints describe the way in which the Xi must
relate to each other.

Applications of Backtracking:

 N Queens Problem
 Sum of subsets problem
 Graph coloring
 Hamiltonian cycles.

bphanikrishna.wordpress.com 4 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

N-Queens Problem:
It is a classic combinatorial problem. The eight queen’s puzzle is the problem of placing eight
queens puzzle is the problem of placing eight queens on an 8×8 chessboard so that no two
queens attack each other. That is so that no two of them are on the same row, column, or
diagonal.

The 8-queens puzzle is an example of the more general n-queens problem of placing n queens
on an n×n chessboard.

Here queens can also be numbered 1 through 8

Each queen must be on a different row

Assume queen ‘i’ is to be placed on row ‘i’

All solutions to the 8-queens problem can therefore be represented a s s-tuples(x1, x2, x3—x8)

xi the column on which queen ‘i’ is placed

si{1, 2, 3, 4, 5, 6, 7, 8}, 1 ≤ i ≤8

Therefore the solution space consists of 88 s-tuples.

The implicit constraints for this problem are that no two xi’s can be the same column and no
two queens can be on the same diagonal.

By these two constraints the size of solution pace reduces from 88 tuples to 8! Tuples.

Form example si(4,6,8,2,7,1,3,5)

In the same way for n-queens are to be placed on an n×n chessboard, the solution space
consists of all n! Permutations of n-tuples (1,2,----n).

bphanikrishna.wordpress.com 5 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Some solution to the 8-Queens problem

Algorithm for new queen be placed All solutions to the n·queens problem

Algorithm Place(k,i) Algorithm NQueens(k, n)

//Return true if a queen can be placed in kth // its prints all possible placements of n-
row & ith column queens on an n×n chessboard.
//Other wise return false {
{ for i:=1 to n do{
for j:=1 to k-1 do if Place(k,i) then
if(x[j]=i or Abs(x[j]-i)=Abs(j-k))) {
then return false X[k]:=I;
return true if(k==n) then write (x[1:n]);
} else NQueens(k+1, n);
}
}}

bphanikrishna.wordpress.com 6 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Sum of Subsets Problem:

Given positive numbers wi 1 ≤ i ≤ n, & m, here sum of subsets problem is finding all subsets
of wi whose sums are m.

Definition: Given n distinct +ve numbers (usually called weights), desire (want) to find all
combinations of these numbers whose sums are m. this is called sum of subsets problem.

To formulate this problem by using either fixed sized tuples or variable sized tuples.

Backtracking solution uses the fixed size tuple strategy.

For example:
If n=4 (w1, w2, w3, w4)=(11,13,24,7) and m=31.
Then desired subsets are (11, 13, 7) & (24, 7).

bphanikrishna.wordpress.com 7 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

The two solutions are described by the vectors (1, 2, 4) and (3, 4).

In general all solution are k-tuples (x1, x2, x3---xk) 1 ≤ k ≤ n, different solutions may have
different sized tuples.
 Explicit constraints requires xi ∈ {j / j is an integer 1 ≤ j ≤ n }
 Implicit constraints requires:
No two be the same & that the sum of the corresponding wi’s be m
i.e., (1, 2, 4) & (1, 4, 2) represents the same. Another constraint is xi<xi+1 1 ≤ i ≤ k

Wi weight of item i

M Capacity of bag (subset)
Xi the element of the solution vector is either one or zero.
Xi value depending on whether the weight wi is included or not.
If Xi=1 then wi is chosen.
If Xi=0 then wi is not chosen.

The above equation specify that x1, x2, x3, --- xk cannot lead to an answer node if this
condition is not satisfied.

The equation cannot lead to solution.

bphanikrishna.wordpress.com 8 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Recursive backtracking algorithm for sum of subsets problem

Algorithm SumOfSub(s, k, r)
{

X[k]=1
If(S+w[k]=m) then write(x[1: ]); // subset found.
Else if (S+w[k] + w{k+1] ≤ M)
Then SumOfSub(S+w[k], k+1, r-w[k]);
if ((S+r - w{k] ≥ M) and (S+w[k+1] ≤M) ) then
{
X[k]=0;
SumOfSub(S, k+1, r-w[k]);
}
}

Graph Coloring:
Let G be a undirected graph and ‘m’ be a given +ve integer. The graph coloring problem is
assigning colors to the vertices of an undirected graph with the restriction that no two
adjacent vertices are assigned the same color yet only ‘m’ colors are used.

The optimization version calls for coloring a graph using the minimum number of coloring.

The decision version, known as K-coloring asks whether a graph is colourable using at most
k-colors.

Note that, if ‘d’ is the degree of the given graph then it can be colored with ‘d+1’ colors.

The m- colorability optimization problem asks for the smallest integer ‘m’ for which the
graph G can be colored. This integer is referred as “Chromatic number” of the graph.

bphanikrishna.wordpress.com 9 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Example

 Above graph can be colored with 3 colors 1, 2, & 3.

 The color of each node is indicated next to it.
 3-colors are needed to color this graph and hence this graph’ Chromatic
Number is 3.
 A graph is said to be planar iff it can be drawn in a plane (flat) in such a way that no
two edges cross each other.
 M-Colorability decision problem is the 4-color problem for planar graphs.
 Given any map, can the regions be colored in such a way that no two adjacent regions
have the same color yet only 4-colors are needed?
 To solve this problem, graphs are very useful, because a map can easily be
transformed into a graph.
 Each region of the map becomes a node, and if two regions are adjacent, then the
corresponding nodes are joined by an edge.

o Example:

o
The above map requires 4 colors.
 Many years, it was known that 5-colors were required to color this map.
 After several hundred years, this problem was solved by a group of mathematicians
with the help of a computer. They show that 4-colors are sufficient.

bphanikrishna.wordpress.com 10 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Suppose we represent a graph by its adjacency matrix G[1:n, 1:n]

Ex:

Here G[i, j]=1 if (i, j) is an edge of G, and G[i, j]=0 otherwise.

Colors are represented by the integers 1, 2,---m and the solutions are given by the n-tuple (x1,
x2,---xn)
xi Color of node i.

State Space Tree for

n=3 nodes
m=3colors

1st node coloured in 3-ways

2nd node coloured in 3-ways
3rd node coloured in 3-ways
So we can colour in the graph in 27 possibilities of colouring.

bphanikrishna.wordpress.com 11 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Finding all m-coloring of a graph Getting next color

Algorithm mColoring(k){ Algorithm NextValue(k){
// g(1:n, 1:n) boolean adjacency matrix. //x[1],x[2],---x[k-1] have been assigned
// kindex (node) of the next vertex to integer values in the range [1, m]
color. repeat {
repeat{ x[k]=(x[k]+1)mod (m+1); //next highest
nextvalue(k); // assign to x[k] a legal color. color
if(x[k]=0) then return; // no new color if(x[k]=0) then return; // all colors have
possible been used.
if(k=n) then write(x[1: n]; for j=1 to n do
else mcoloring(k+1); {
} if ((g[k,j]≠0) and (x[k]=x[j]))
until(false) then break;
} }
if(j=n+1) then return; //new color found
} until(false)
}

bphanikrishna.wordpress.com 12 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Previous paper example:

Adjacency matrix is

bphanikrishna.wordpress.com 13 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

Hamiltonian Cycles:
 Def: Let G=(V, E) be a connected graph with n vertices. A Hamiltonian cycle is a
round trip path along n-edges of G that visits every vertex once & returns to its
starting position.
 It is also called the Hamiltonian circuit.
 Hamiltonian circuit is a graph cycle (i.e., closed loop) through a graph that visits each
node exactly once.
 A graph possessing a Hamiltonian cycle is said to be Hamiltonian graph.
Example:

 In graph G, Hamiltonian cycle begins at some vertiex v1 ∈ G and the

vertices of G are visited in the order v1,v2,---vn+1, then the edges (vi, vi+1) are
in E, 1 ≤ i ≤ n.

g1
The above graph contains Hamiltonian cycle: 1,2,8,7,6,5,4,3,1

The above graph contains no Hamiltonian cycles.

 There is no known easy way to determine whether a given graph contains a

Hamiltonian cycle.
 By using backtracking method, it can be possible
 Backtracking algorithm, that finds all the Hamiltonian cycles in a graph.
 The graph may be directed or undirected. Only distinct cycles are output.

bphanikrishna.wordpress.com 14 Department of C.S.E

 DESIGN AND ANALYSIS OF ALGORITHMS (UNIT-VI @ Backtracking)

 From graph g1 backtracking solution vector= {1, 2, 8, 7, 6, 5, 4, 3, 1}

 The backtracking solution vector (x1, x2, --- xn)
xi ith visited vertex of proposed cycle.
 By using backtracking we need to determine how to compute the set of
possible vertices for xk if x1,x2,x3---xk-1 have already been chosen.
If k=1 then x1 can be any of the n-vertices.
By using “NextValue” algorithm the recursive backtracking scheme to find all Hamiltoman
cycles.
This algorithm is started by 1st initializing the adjacency matrix G[1:n, 1:n] then setting x[2:n] to
zero & x[1] to 1, and then executing Hamiltonian (2)
Generating Next Vertex Finding all Hamiltonian Cycles
Algorithm NextValue(k) Algorithm Hamiltonian(k)
{ {
// x[1: k-1] is path of k-1 distinct vertices. Repeat{
// if x[k]=0, then no vertex has yet been NextValue(k); //assign a legal next value to
assigned to x[k] x[k]
Repeat{ If(x[k]=0) then return;
X[k]=(x[k]+1) mod (n+1); //Next vertex If(k=n) then write(x[1:n]);
If(x[k]=0) then return; Else Hamiltonian(k+1);
If(G[x[k-1], x[k]]≠0) then } until(false)
{ }
For j:=1 to k-1 do if(x[j]=x[k]) then break;
//Check for distinctness
If(j=k) then //if true , then vertex is distinct
If((k<n) or (k=n) and G[x[n], x[1]]≠0))
Then return ;
}
}
Until (false);
}

bphanikrishna.wordpress.com 15 Department of C.S.E