Back Tracking

Backtracking: Idea
• Backtracking is a technique used to solve problems with a large
search space, by systematically trying and eliminating
possibilities.
• A standard example of backtracking would be going through a
maze.
– At some point, you might havePortion A of which direction to go:
two options
Junction
Portion B
 Backtracking
o n
cti
One strategy would be to try going through Jun
Portion A of the maze.
If you get stuck before you find your Portion B
way out, then you "backtrack" to the
junction.

Portion A
At this point in time you know that Portion A
will NOT lead you out of the maze,
so you then start searching in Portion B
 Backtracking
• Clearly, at a single junction you
could have even more than 2
choices.

• The backtracking strategy says to

try each choice, one after the n
ti o
other, n c
– if you ever get stuck, "backtrack" to Ju C
the junction and try the next choice. B
A
• If you try all choices and never
found a way out, then there IS no
solution to the maze.
 Backtracking (animation)
dead end

?
dead end
dead end

?
start ? ?
dead end

dead end

success!
 Backtracking
• Dealing with the maze:
– From your start point, you will iterate through each
possible starting move.
– From there, you recursively move forward.
– If you ever get stuck, the recursion takes you back to
where you were, and you try the next possible move.

• Make sure you don't try too many possibilities,

– Mark which locations in the maze have been visited
already so that no location in the maze gets visited twice.
– If a place has already been visited, there is no point in
trying to reach the end of the maze from there again.
 Backtracking

The neat thing about coding up backtracking is

that it can be done recursively, without having
to do all the bookkeeping at once.
– Instead, the stack of recursive calls does most of
the bookkeeping
– (i.e., keeps track of which locations we’ve tried so
far.)
 General Method:
• In the search for fundamental principles of algorithm design,
backtracking represents one of the most general techniques.
• Many problems which deal with searching for a set of
solutions or which ask for an optimal solution satisfying some
constraints can be solved using the backtracking formulation.
• In many applications of the backtrack method, the desired
solution is expressible as an n-tuple (x1 to xn),where xi are
chosen from some finite set Si.
• Often the problem to be solved calls for finding one vector
that maximizes (or minimizes or satisfies) a criterion function
P(x1, ... , xn ).
 General Method:
• Often the problem to be solved calls for finding
one vector that maximizes (or minimizes or
satisfies) a criterion function P(x1 ... xn )-
Sometime its seeks all vectors that satisfy P.
• Sometime its seeks all vectors that satisfy P.
• For example sorting the array of integers in a[l:
n] is a problem whose solution is expressible by
an n tuple where x is the index in a of the ith
smallest element
 General Method:
• Sometimes it seeks all the vectors that satisfies P.
• For example sorting the array of integers in a[l: n] is
a problem whose solution is expressible by an n
tuple, where 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.
• The set Sj is finite and includes the integers 1
through n.
 General Method:
• Though sorting is not usually one of the problems solved by
backtracking, it is one example of a familiar problem whose
solution can be formulated as an n-tuple.
• Suppose mi is the sizeof set xi Then there are m = m1, m2... 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
backtrack algorithm has as its virtue the ability to yield the same
answer with far fewer than m trials. Its basic idea is to build up
the solution vector one component at a time and to use modified
criterion functions Pi (x1, ... Xi ) sometimes called as bounding
functions to test whether the vector formed is having any chance
of success.
 General Method:
• The major advantage of this method is this :if it is
realized that the partial vector (x 1, ... Xi ) can in no
way lead to an optimal solution,
• then Mi+1 ... Mn possible test vectors can be ignored
entirely.
• Many of the problems we solve using backtracking
require that all the solutions satisfy a complex set of
constraints. For any problem these constraints can
be divided into two categories explicit and implicit
 General Method:
• Explicit constraints are rules that restrict each X i to take
on values only from given set.
• Common examples of explicit constraints are
• 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 constraints depend on the particular
instance I of the problem being solved.
• All tuples that satisfy the explicit constraints define a
possible solution space for I
 General Method:
• The implicit constraints are rules that
determine which of the tuples in the solution
space of I satisfies the criterion function.
• Thus implicit constraints describe the way in
which Xi must relate to each other.
 Backtracking
• 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 (possibly more than one)
may be a solution to your problem
• Backtracking is a methodical way of trying out
various sequences of decisions, until you find the
correct one that “works”.
 Backtracking
• Backtracking is used to solve problems in which
a sequence of objects is chosen from a specified
set so that the sequence satisfies some criterion.
• Backtracking is a modified depth-first search of a
tree.
• It is the procedure whereby, after determining
that a node can lead to nothing but dead nodes,
we go back (“backtrack”) to the node’s parent
and proceed with the search on the next child.
 Backtrack Algorithm

• Based on depth-first recursive search

• Approach
1. Tests whether solution has been found
2. If found solution, return it
3. Else for each choice that can be made
a) Make that choice
b) Recursive
c) If recursion returns a solution, return it
4. If no choices remain, return failure
• Some times called “search tree”
 Improving Backtracking
• Search pruning will help us to reduce the
search space and hence get a solution faster.

• The idea is to avoid those paths that may not

lead to a solutions as early as possible by
finding contradictions so that we can
backtrack immediately without the need to
build a hopeless solution vector.
Backtracking EXAMPLE—8 Queens Problem

• The 8-queens problem is a classical

combinatorial problem in which it is required to
place eight queens on an 8 x 8 chessboard so
no two can attack each other.

• A queen can attack another queen if it exists in

the same row, column or diagonal as the
queen.
19
 Backtracking EXAMPLE—8 Queens
Problem(cont…)
• This problem can be solved by trying to place
the first queen, then the second queen so that
it cannot attack the first, and then the third so
that it is not conflicting with previously placed
queens.
Backtracking EXAMPLE—8 Queens
Problem(cont…)

• It is an empty 8 x 8
chess board. We have
to place the queens in
this board.
Backtracking EXAMPLE—8 Queens
Problem(cont…)

• We have placed the first

queen on the chess
board
Backtracking EXAMPLE—8 Queens
Problem(cont…)
• Then we have placed
the second queen on
the board.
• The darken place should
not have the queens
because they are
horizontal, vertical,
diagonal to the placed
queens.
Backtracking EXAMPLE—8 Queens
Problem(cont…)

• We have placed the

third queen on board.
Backtracking EXAMPLE—8 Queens
Problem(cont…)

• We have placed the 4th

queen on the board.
• We have placed that in
the wrong spot, so we
backtrack and change
the place of that one.
 Backtracking EXAMPLE—8 Queens
Problem(cont…)
• In this way, we have to
continue the process
untill our is reached ie.,
we must place 8 queens
on the board.
 Backtracking EXAMPLE—8 Queens
Problem(cont…)
– Backtracking provides the hope to solve some problem
instances of nontrivial sizes by pruning non-promising
branches of the state-space tree.

– The success of backtracking varies from problem to

problem and from instance to instance.

– Backtracking possibly generates all possible candidates in

an exponentially growing state-space tree.
 Graph Coloring Problem
• The goal is to color vertices in a graph G={V,E} so that no 2 adjacent vertices
have the same color. Partial 3-coloring problem means only 3 colors are
considered.
• Direct approach builds the tree of ALL possibilities in exponential time.

28
 Backtracking
• Partial 3-coloring (3 colors) is solved by the following method:
• Color first vertex with 1st color, color next vertex with the next color, check if
those two vertices are adjacent, if not - coloring is legal, proceed to next
vertex, if yes and color is the same – coloring is illegal, try next color for
second vertex. If all colors tried and all colorings are illegal, backtrack, try next
color for previous vertex etc.
• Note: sometimes solution is impossible.
• Exponential O(3^n) complexity is reduced to O(n) on average.

29
 Backtracking
• The goal is to color vertices in a graph G={V,E} so that no 2 adjacent vertices
have the same color. Partial 3-coloring problem means only 3 colors are
considered.
• Direct approach builds the tree of ALL possibilities in exponential time.

30
 Backtracking
• Partial 3-coloring (3 colors) is solved by the following method:
• Color first vertex with 1st color, color next vertex with the next color, check if
those two vertices are adjacent, if not - coloring is legal, proceed to next
vertex, if yes and color is the same – coloring is illegal, try next color for
second vertex. If all colors tried and all colorings are illegal, backtrack, try next
color for previous vertex etc.
• Note: sometimes solution is impossible.
• Exponential O(3^n) complexity is reduced to O(n) on average.

31
 Recursive backtracking Algorithm:
1. Algorithm Backtrack (k)
2. // This schema describes the backtracking
process using recursion.
3. // On entering, the first k-1 values
4. // X[1]. X[2], ... X[ k-1] of the solution vector
5. // x[1:n] have been assigned. X[] and n are
global
 Recursive backtracking Algorithm:
6. {
7. For each x[k] E T (x[1],... X[k-1]) do
8. {
9. if Bk (x[1],x[2],... X[k] !=0) then
10. {
11. if (x[1], x[2],... X[k] is a path to answer the code)
12. then write (x[1:k]);
13. If (k<n) then backtrack (k+1)
14. }
15. }
16. }
 Iterative backtracking Algorithm:
1. Algorithm Ibacktrack (n)
2. // This schema describes the backtracking
process.
3. // All the solutions are generated in x[1:n] and
printed
4. // as soon as they are determined.
5. {
6. k=1;
7. while (k!=0)
 Iterative backtracking Algorithm:
8. {
9. if (there remains an untried x[k] E T)x[1], x[2],..., x[k-1])
and Bk (x[1],..., x[k]) is true) then
10. {
11. if x[1],... X[k] is a path to answer node)
12. Then write ( x[1:k]);
13. K= k+1// Consider the next set
14. }
15. else k= k-1 // Backtrack to the previous track
16. }
17. }
 Queen’s Placement Algorithm
1. Algorithm Place (k,i)
2. // Returns true if a queen can be placed in
kth row and ith column.
3. // Otherwise it returns false.
4. // x[] is a global array whose first (k-1) values
have been set.
5. // Abs (r) returns the absolute value of r.
6. {
 Queen’s Placement Algorithm
7. For j=1 to k-1 do
8. if (x[j]=i) // two in the same column
9. or Abs9x[j]-i = Abs(j-k)))
10. // or in same digonal
11. then return false;
12. return true
13. }
 N-Queen’s Placement Algorithm
1. Algorithm Nqueens (k,n)
2. // Using backtracking, this procedure prints
all
3. // possible placements of n-queens on nxn
4. //chessboard so that they are nonattacking
5. {
6. for i= 1 to n do
7. {
 N-Queen’s Placement Algorithm
8. If place(k,i) then
9. {
10. x[k]= i
11. if (k=n) then write (x[1:n])
12. else Nqueens (k+1, n);
13. }
14.}
15.}
 Sum of Subsets:
• Suppose we are given n distinct positive numbers
(usually called weights) and we desire to find all
combinations of these numbers whose sums are m.
• This type of problems are called as Sum of subsets
problem.
• A simple choice for a bounding functions is
Bk (x1,... , xk ) = true iff
k n
Ʃ wi xi + Ʃ wi >=m
i=1 i=k+1
 Algorithm Sum of Subsets:
1. Algorithm SumOfSub(s,k,r)
2. // Find all subsets of w[1:n] that sum to m.
3. // The values of x[j], 1<-j<k, have already
n
been determined s= Ʃ
Algorithm Sum of Subsets: