Backtracking Algorithm

Backtracking
•It is a systematic way to search for a solution to a problem
among all available options in a search space.
•It does so by assuming that the solutions are represented
by vectors (v1, ..., vm) of values and by traversing, in a
depth first manner, the domains of the vectors until the
solutions are found.
– Often the problem to be solved calls for finding one
vector that maximizes (or minimizes or satisfies) a
criterion function P(x1, ..., xm).
•We build from a partial solution of length k, v = (a1, ..., ak)
and try to extend it by adding another element. After
extending it, we will test whether what we have so far is
still possible as a partial solution.
– If it is still a candidate solution, great. If not, we delete
ak and try the next element from Sk:
Backtracking approach
• An important requirement in backtracking is that there
must be proper hierarchy in systematically searching for
solutions so that sets of solutions that do not fulfill a
certain requirement are rejected before the solutions are
produced.
– For this reason the examination and production of the
solutions follows a model of non-cycle graph for
which in this case we will consider as a tree.
– It is easily understood that the tree (or any other
graph) is produced during the examination of the
solutions so that no rejected solutions are produced.
– When a node is rejected, the whole sub-tree is
rejected, and we backtrack to the ancestor of the node
so that more children are produced and examined.
The Queens Problem
• Consider a n by n chess board, and the problem of placing
n queens on the board without the queens threatening one
another.
• The solution space is {1, 2, 3,…, n}n.
The backtracking algorithm may
record the columns where the
different queens are positioned.
Trying all vectors (p1, ..., pn) implies
nn cases queens threatening one
another.
• Noticing that all the queens must reside in different
columns reduces the number of cases to n!
• For the latter case, the root of the traversal tree has degree
n, the children have degree n - 1, the grand children degree
n - 2, and so forth.
How backtracking works
• As a bounding function we use if (x1, ..., xi) is the path to the current
E-node (node being expanded), then all children nodes with parent-
child labeling xi+1 are such that (x1, ..., xi+1) represents the chessboard
configuration in which no two queens are attacking.
• Start with the root node as the only live node.
–This become the E-node and the path is ().
• Generate one child (say 2).
–The path is now (1), which corresponds to placing queen 1 on
column 1.
–Node 2 becomes the E-node. Node 3 is then generated
• If the node is attacked by the previous node, the path is
immediately killed
• Otherwise add to the path list (1, 2) and generate the next node.
–If the path cannot lead to an answer node then backtrack and try
another path.
4 - Queens
•The problem is to place four queens on an 4
x 4 chessboard so that
–No two attack, i.e. no two of them are on
the same row, column or diagonal.

Initial 4 x 4 chessboard
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
Algorithm for n-queens
•Let (x1, ..., xn) represent a solution in which xi is the
column of the ith row where the ith queen is placed.
•All xi’s be distinct since no two queens can be
placed in the same column.

– Computing time = 0 + 1 + 2 + … + (n-1)

Algorithm
procedure NQueens(k,n)
for i = 1 to n do
if place(k,i) then
x[k] = i
if k = n then print (x[1:n])
else NQueens(k+1, n)
end if
end for
end NQueens
procedure place(k,i) //returns true if a queen is placed at (k,i)
for j = 1 to k-1 do
if (x[j] = i) or ((abs(x[j] - i) = (abs(j - k)) then
//two in the same column or in the same diagonal
return false
return true
end place
Graph Coloring
• What is Graph Coloring Problem?
• We have been given a graph and we are asked to color all
vertices with the ‘M’ number of given colors, in such a way
that no two adjacent vertices should have the same color.

• It is possible to color all the vertices with the given colors then
we have to output the colored result, otherwise output ‘no
solution possible’.
• The least possible value of ‘m’ required to color the graph
successfully is known as the chromatic number of the given
graph.
Graph Coloring Solution
• Using Naive Algorithm
• In this approach using the brute force method, we
find all permutations of color combinations that can
color the graph.
• If any of the permutations is valid for the given graph
and colors, we output the result otherwise not.
• This method is not efficient in terms of time
complexity because it finds all colors combinations
rather than a single solution.
Cont..
• Using Backtracking Algorithm
• The backtracking algorithm makes the process efficient by
avoiding many bad decisions made in naïve approaches.
• In this approach, we color a single vertex and then move to its
adjacent (connected) vertex to color it with different color.
• After coloring, we again move to another adjacent vertex that is
uncolored and repeat the process until all vertices of the given
graph are colored.
• In case, we find a vertex that has all adjacent vertices colored and
no color is left to make it color different, we backtrack and change
the color of the last colored vertices and again proceed further.
• If by backtracking, we come back to the same vertex from where
we started and all colors were tried on it, then it means the given
number of colors (i.e. ‘m’) is insufficient to color the given graph
and we require more colors (i.e. a bigger chromatic number).
Cont..
• Algorithm To color graph using the Backtracking:
1. Different colors:
A. Confirm whether it is valid to color the current vertex with the current color
(by checking whether any of its adjacent vertices are colored with the same
color).
B. If yes then color it and otherwise try a different color.
C. Check if all vertices are colored or not.
D. If not then move to the next adjacent uncolored vertex.
2. If no other color is available then backtrack (i.e. un-color last
colored vertex).
• Here backtracking means to stop further recursive calls on adjacent
vertices by returning false. In this algorithm Step-1.2 (Continue)
and Step-2 (backtracking) is causing the program to try different
color option.
• Continue – try a different color for current vertex.
• Backtrack – try a different color for last colored vertex.
Cont..
Hamiltonian Cycle
• The Hamiltonian cycle is the cycle in the graph which visits all
the vertices in graph exactly once and terminates at the starting
node. It may not include all the edges.
• The Hamiltonian cycle problem is the problem of finding a
Hamiltonian cycle in a graph if there exists any such cycle.
• The input to the problem is an undirected, connected graph.
For the graph shown in Figure below, a path A – B – E – D –
C – A forms a Hamiltonian cycle. It visits all the vertices
exactly once, but does not visit the edges <B, D>.
Cont..
• The Hamiltonian cycle problem is also both, decision problem
and an optimization problem. A decision problem is stated as,
“Given a path, is it a Hamiltonian cycle of the graph?”.
• The optimization problem is stated as, “Given graph G, find
the Hamiltonian cycle for the graph.”
• We can define the constraint for the Hamiltonian cycle
problem as follows:
✓ In any path, vertex i and (i + 1) must be adjacent.
✓ 1st and (n – 1)th vertex must be adjacent (nth of cycle is the
initial vertex itself).
✓ Vertex i must not appear in the first (i – 1) vertices of any
path.
• With the adjacency matrix representation of the graph, the
adjacency of two vertices can be verified in constant time.
Cont..
Algorithm for finding a Hamiltonian cycle using
backtracking:
[Link] with an arbitrary vertex v as the starting point.
[Link] v is the last vertex in the cycle and all vertices have been
visited, then return the cycle.
[Link] each unvisited vertex adjacent to v, add it to the cycle,
mark it as visited, and recursively search for a Hamiltonian
cycle starting from the new vertex.
[Link] the search fails, remove the vertex from the cycle and
mark it as unvisited.
[Link] all adjacent vertices have been tried and none of them
leads to a Hamiltonian cycle, return failure.
Cont..
• Example: Show that given graph has a Hamiltonian cycle.

Solution:
• We can start with any random vertex. Let us start with vertex A.
Neighbors of A are {B, C, D}. The inclusion of B does not lead
to a complete solution.
• Adjacent vertices to B are {C, D}. The inclusion of C does not
lead to a complete solution. All adjacent vertices of C are already
members of the path formed so far. So it leads to a dead end.
• Backtrack and go to B and explore its next neighbor i.e. D.
• The inclusion of D does not lead to a complete solution, and all
adjacent vertices of D are already a member of the path formed
so far. So it leads to a dead end.
Cont..

dead-end dead-end
• Backtrack and go to B. Now B does not have any more
neighbors, so backtrack and go to A. Explore the next neighbor
of A i.e. C. By repeating the same procedure, we get the state
space trees as shown below. And path A – C – B – D – A is
detected as the Hamiltonian cycle of the input graph.

Another Hamiltonian cycle with A

as a start vertex is A – D – B – C – A.
Cont..
• Example: Explain how to find Hamiltonian Cycle by
using Backtracking in a given graph.
Traveling Salesperson Problem (TSP)
• The problem assumes a set of n cities, and a salesperson
which needs to visit each city exactly once and return to
the base city at the end.
– The solution should provide a route of minimal length.
• The traveling salesperson problem is an NP-hard problem,
and so no polynomial time algorithm is available for it.
– Given an instance G = (V, E) the backtracking
algorithm may search for a vector of cities (v1, ..., v|V |)
which represents the best route.
• The validity criteria may just check for number of cities in
the routes, runing out routes longer than |V |. In such a
case, the algorithm needs to investigate |V ||V | vectors
from the solution space.
Traveling Salesperson

• On the other hand, the validity

criteria may check for repetition
of cities, in which case the
number of vectors reduces to |V
|!.
– That is, complexity = n!
Traveling Salesperson
• Given the following problem,
starting from city a apply
backtracking algorithm to find
the shortest path to visit all cities
(and back to city a).

•The route (a, b, d, c) is the shortest one

with length = 51.
•Can we reach to this decision using
backtracking algorithm ?
Backtracking
• Effective for decision problems.
• Systematically traverse through possible paths to
locate solutions or dead ends
• At the end of the path, algorithm is left with (x, y)
pair. x is remaining subproblem, y is set of choices
made to get to x
• Initially (x, Ø) passed to algorithm
Algorithm Backtrack(x):
Input: A problem instance x for a hard problem
Output: A solution for x or “no solution” if none exists
F• {(x, Ø)}.
while F ≠ Ø do
select from F the most “promising” configuration (x, y)
expand (x, y) by making a small set of additional choices
let (x1, y1), …, (xk, yk) be the set of new configurations.
for each new configuration (xi, yi) do
perform a simple consistency check on (xi, yi)
if the check returns “solution found” then
return the solution derived from (xi, yi)
if the check returns “dead end” then
discard the configuration (xi, yi)
else
F• F U {(xi, yi)}.
return “no solution”
Algorithm Design Challenge
• Given three arrays of n real numbers (the
numbers can be positive or negative), write an
algorithm to determine if there are three
numbers, one from each array whose sum is 0.
Design the most efficient algorithm you can
think of to solve this problem. It can be done
in O(n2) time.

51