Downloaded from be.rgpvnotes.

in

Unit-4 Backtracking

Introduction:
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 do t ha e e ough i fo atio to k o hat to hoose
 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
fi d o e that o ks
Example@1 : Maze (a tour puzzle)

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

1. In maze, at each intersection, you have to decide between 3 or fewer choices:
 Go straight
 Go left
 Go right
2. You do t ha e e ough i fo atio to hoose o e tl
3. Each choice leads to another set of choices.
4. One or more sequences of choices may or may not lead to a solution.
5. Many types of maze problem can be solved with backtracking.

Example@ 2
Sorting the array of integers in a[1:n] is a problem whose solution is expressible by an n-tuple xi is
the inde i a of the ith smallest element.
The ite io fu tio P is the i e ualit a[ i] a[ i+1] fo i
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.
B usi g a kt a k algo ith ; ield the sa e a s e ith fa fe e tha t ails.
Many of the problems we solve using backtracking requires that all the solutions satisfy a complex

Page no: 1 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

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

Page no: 2 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

N-Queens Problem:

It is a classic combinatorial problem. The eight uee s puzzle is the p o le of pla i g 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
Assu e uee i is to e pla ed o o i

All solutions to the 8-queens problem can therefore be represented a s s-tuples(x1, x2, x3—x8)
i= the olu o hi h uee i is pla ed
si={ , , , , , , , }, i
Therefore the solution space consists of 88 s-tuples.
The implicit constraints for this problem are that no two xi s a e the sa e olu a d ot o
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).

Page no: 3 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

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);
}
}}

Page no: 4 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

Sum
of
Subs
ets
Probl
em:
Given
positi
ve
numb
ers wi
i
,
& m,
here
sum
of
subse
ts
probl
em is
findin
g all
subse
ts 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).
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 k , diffe e t solutio s a ha e diffe e t
sized tuples.
 Explicit constraints requires xi ∈ {j / j is a i tege j }
 Implicit constraints requires:
No two be the same & that the sum of the corresponding wi s e
i.e., (1, 2, 4) & (1, 4, 2) represents the same. Another constraint is x i<xi+1 i k

Wi= weight of item i

M= Capacity of bag (subset)

Page no: 5 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

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.

Page no: 6 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

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 “+ [k] + {k+ ] M
Then SumOfSub(S+w[k], k+1, r-w[k]);
if ((S+r - {k] M a d “+ [k+ ] M the
{
X[k]=0;
SumOfSub(S, k+1, r-w[k]);
}
}

Hamiltonian Cycle:

 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 a e i E, i .

Page no: 7 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

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.
 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.
B usi g Ne tValue algo ith the e u si e a kt a ki g s he e to fi d all Ha ilto a les.
st
This algorithm is started by 1 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- ], [k]]≠ the } 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< o k= a d G[ [ ], [ ]]≠
Then return ;
}
}
Until (false);
}

Page no: 8 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

Graph Coloring:

Let G e a u di e ted g aph a d e a gi e + e i tege . The g aph olo i g p o le is assig i g

colors to the vertices of an undirected graph with the restriction that no two adjacent vertices are
assig ed the sa e olo et o l olo s a e 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 deg ee of the gi e g aph the it a e olo ed ith d+ olo s.
The m- olo a ilit opti izatio p o le asks fo the s allest i tege fo hi h the g aph G
a e olo ed. This i tege is efe ed as Chromatic number of the graph.
Example

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


The color of each node is indicated next to it.
3- olo s a e eeded to olo this g aph a d he e this g aph Ch o ati Nu e is .
 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:

Page no: 9 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

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

Page no: 10 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

2nd node coloured in 3-ways

3rd node coloured in 3-ways
So we can colour in the graph in 27 possibilities of colouring.
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]≠ a d [k]= [j]
until(false) then break;
} }
if(j=n+1) then return; //new color found
} until(false)
}

Previous paper example:

Adjacency matrix is

Page no: 11 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

15 puzzle Problem:

The "15 puzzle" is a sliding square puzzle commonly (but incorrectly) attributed to Sam Loyd
The 15 puzzle consists of 15 squares numbered from 1 to 15 that are placed in a box leaving
one position out of the 16 empty. The goal is to reposition the squares from a given arbitrary
starting arrangement by sliding them one at a time into the final configuration .
In general, for a given grid of width N, we can find out check if a N*N – 1 puzzle is solvable or not
by following below simple rules :

 If N is odd, then puzzle instance is solvable if number of inversions is even in the input
state.
 If N is even, puzzle instance is solvable if
◦ the blank is on an even row counting from the bottom (second-last, fourth-last, etc.)
and number of inversions is odd.
◦ the blank is on an odd row counting from the bottom (last, third-last, fifth-last, etc.)
and number of inversions is even.
 For all other cases, the puzzle instance is not solvable.

What is an inversion here?

If we assume the tiles written out in a single row (1D Array) instead of being spread in N-rows (2D
Array), a pair of tiles (a, b) form an
inversion if a appears before b but
a > b.

Page no: 12 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

Example:
8-puzzle
Cost function: Ĉ = g(x) +h(x)
where h(x) = the number of misplaced tiles
and g(x) = the number of moves so far
Assumption: move one tile in any direction cost 1.

Page no: 13 Follow us on facebook to get real-time updates from RGPV

Downloaded from be.rgpvnotes.in

LEAST COST SEARCH

A sea h st ateg that uses a ost fu tio ĉ = f h + ĝ to sele t the e t E-node would
always choose for its next E- ode a li e ode ith least ĉ ·
∗ Such a search strategy is called an LC -search (Least Cost search)
∗ Both BFS and DFS are special cases of LC -search
∗ I BF“ , e use ĝ ≡ a d f h as the le el of ode .LC sea h ge e ates odes le el
∗ I DF“ , e use f h ≡ a dĝ ĝ he e e is a hild of
– An LC -search coupled with bounding functions is called an LC branch-and-bound search

Cost function:

ĉ =f h +ĝ

where h(x) is the cost of reaching x from root

ĝ(x) be an estimate of the additional effort needed to reach an answer from node x

 If x is an answer node, c(x) is the cost of reaching x from the root of state space tree
 If is ot a a s e ode, = ∞, p o ided the su t ee o tai s o a s e ode
 If subtree x contains an answer node, c(x) is the cost of a minimum cost answer node in
subtree x

Page no: 14 Follow us on facebook to get real-time updates from RGPV