Backtracking

Dr. Dinesh Reddy

Backtracking (Real Scenario
Example)
• Have you ever seen Blind people walking on road?

❑ If Blind people find any obstacles in

their way, they jut move backword and
then they will proceed in other
direction.
❑ How a blind person could move
backward when he/she finds obstacle?
❑ Simple answer…. By intelligence !!
❑ Similarly, if an algorithm Backtracks
with intelligence, it is called a
“Backtracking Algorithm”.
Backtracking Approach: Introduction
• Suppose we have to make a series of decisions, among various choices
where we don’t have enough information to know what to choose and each
decision leads to a new set of choices.

• Some sequence of choices (possibly more

than one) may be a solution to our problem.

• Backtracking is a methodical way of trying

out various sequences of decisions until we
find one that “works”.

• Backtracking Algorithm determines soln by

systematically searching the solution space
for given problem. It is a “Depth First
Search” with some bounding function.
Terminology I
A tree is composed of nodes

There are three kinds of nodes:

The (one) root node

Backtracking can be thought of as
Internal nodes
searching a tree for a particular “goal”
Leaf nodes leaf node
Terminology II

• Each non-leaf node in a tree is a parent of one

or more other nodes (its children)
• Each node in the tree, other than the root, has
exactly one parent parent
Usually, however, we
draw our trees downward,
with the root at the top
parent

children children
Problems solved by Backtracking
Approach or Algorithms
• Example: Maize Problem, N-Queens Problem, Knight’s Tour Problem

Other Problems: Hamiltonian Circuit Problem, Subset-sum Problem, Travelling

Salesman Problem (TSP), Graph Coloring Problem etc.
Coloring a map

• You wish to color a map with

not more than four colors
• red, yellow, green, blue
• Adjacent countries must be in
different colors
• You don’t have enough information to choose colors
• Each choice leads to another set of choices
• One or more sequences of choices may (or may not) lead to
a solution
• Many coloring problems can be solved with backtracking
Applications
• crosswords
• verbal arithmetic
• Hamiltonian Cycle
• M-Coloring Problem
• N Queen Problem
• Rat in Maze Problem
• Cryptarithmetic Puzzle
• Subset Sum Problem
• Sudoku Solving Algorithm
• Knight-Tour Problem
• Tug-Of-War Problem
• Word Break Algorithm
• Maximum number by swapping problem
 The backtracking algorithm
• Backtracking is really quite simple--we “explore” each
node, as follows:
• To “explore” node N:
1. If N is a goal node, return “success”
2. If N is a leaf node, return “failure”
3. For each child C of N,
3.1. Explore C
3.1.1. If C was successful, return “success”
4. Return “failure”
N-Queens Problem

• N-Queens problem is to place N-Queens in such a way on a N x N

chessboard that no two queens attack each other by being in a same row,
column or diagonal. The puzzle was originally proposed in 1848 by the chess
player Max Bezzel.

• It can be seen that for N=1, the

problem has a trivial solution. And
no solution exits for N=2 and N=3.

• So, first we will consider 4-Queens

problem and then generalize it to
N-Queens problem.
4 x 4 chessboard
Problems N < 4

N<4
Cannot use N Queens
3

1
State-Space Tree for 4-Queens Problem
Brute Force Search

Size of search space is N !

Then, how to search effectively??
State-Space Tree for 4-Queens Problem
With Bounding Function
(explore by ensuring no diagonal attack)
4-Queens Problem: Two possible
Solutions…

Soln X = 2 4 1 3 X 3 1 4 2
=
Column no.
https://www.youtube.com/watch?v=0DeznFqrgAI
5-Queens Problem: Many possible
Solutions…
8-Queens Problem
Solutions:
8-Queens Problem: More solutions…

Solution 13:
900 clockwise rotation
of Solution 3

Solution 15:
1800 clockwise/anti-clockwise
rotation of Solution 3
Solution 14:
900 anti-clockwise
rotation of Solution 3

http://www.hbmeyer.de/backtrack/achtdamen/eight.htm#up
 N-Queens Problem: Developing a
Backtracking Algorithm
1. Start from the first row.
2. if all queens are placed return “true”
3. Check all columns in the current row
Do following for every tried column
a) if the queen can be placed safely in this column then mark this position
[row,column] as part of the solution and recursively check if placing
queen here leads to a solution.
b) if placing the queen in [row,column] leads to a solution then return “true”
c) if placing queen doesn’t leads to a solution then unmark this position
[row,column],(means Backtrack) and go to step a) to check other columns.
4. If all columns have been checked and nothing worked,
return “false” to trigger backtracking.
N-Queens Problem: Backtracking Algorithm
Approach (Horowitz and Sahni Book)
You observed from the 8-queens problem that we can let (X1, ... , X ) represent a solution where X is the
n i
column of the ith row where the ith queen is placed. The XiS will all be distinct since no two queens can be
placed in the same column. Now, how do we test if two queens are on the same diagonal?

❑ Thus, the solution for 8-queens problem

is (4, 6, 8, 2, 7, 1, 3, 5).
❑ If two queens are placed at position (i, j) and (k, l).
Then, they are on same diagonal only
if i-j =k-l
or i+j=k+l
The first equation implies that j - l = i - k.
The second equation implies that j - l = k - i
❑ Therefore, two queens lie on the same diagonal if and
only if | j – l |=| i – k |
N-Queens Algorithm –Recursive
Algorithm
N-Queens Problem: Backtracking Algorithm
(Horowitz and Sahni Book)
procedure NQUEENS(n)
// using backtracking this procedure prints all possible placements of n queens
// on an n x n chessboard so that they are non-attacking.
integer k, n, X(1:n)
X(1) 0; k 1 // k is the current row; X(k) is the current column
while k > 0 do // for all rows do
X(k) = X(k) + 1 // move to the next column
while X(k) ≤ n and not PLACE(k) do // call this: can a new queen be placed?
X(k) = X(k) + 1
repeat
if X(k) ≤ n // a potion is found
then if k = n // is a solution complete?
then print(X) // yes, print the solution array
else k = k + 1; X(k) 0 // go to the next row
endif
else k = k - 1; // backtrack
endif
repeat
end NQUEENS
Algorithm: Can a new queen be placed?
procedure PLACE(k)
// return true if a queen can be placed in the kth row and X(k)th column.
// Otherwise it returns false.
// X is a global array whose first k values have been set.
// ABS(r) returns the absolute value of r
global X(1:k); integer i, k
for i 1 to k-1 do
if X(i) = X(k) // two in the same column
or ABS(X(i)- X(k)) = ABS(i-k) // two in the same diagonal
then return (false)
endif
repeat
return(true)
end PLACE

PLACE (k) procedure Computing time = O(k)

Knight’s Tour Problem

• What is Knights Tour?

• The problem is that if” The knight is placed on any
block of an empty chess board and, moving
according to the rules of chess, must visit each
square exactly once.”
• This Problem is an application of Hamiltonian Path
or cycle
Knight’s Tour Problem
• A knight moves two squares horizontally or
vertically and then one square perpendicularly
from its current position.
• In the knight’s tour problem, the goal is to make a
knight visit every position on a chessboard without
visiting any square twice.
• A tour is considered closed if the final position is
one move away from the starting position, and the
knight could immediately start the tour again.
• A tour that is not closed is considered open
KNIGHT – Possible Moves

•
Knight’s Tour
demonstration
on 6 x 6 board

3 Possible Solutions
Knight’s Closed Tour vs. Open Tour
• Finding a knight tour is actually
an application of Hamiltonian
Path or cycle.

• A knight tour is considered

closed if the final position is one
move away from the starting
position, and the knight could
immediately start the tour
again.

• A tour that is not closed is

considered open.
Closed Tour Open Tour
Open Tour Vs Closed Tour
Knight’s Tour demonstration on 8
x 8 board

Example of closed tour

8 x 8 Board
Knights Tour Problem
Knights Tour Problem
Knights Tour Problem

Valid Move:
A move is valid if it is inside the chessboard (i.e., i and j are
between 1 to N) and if the cell is not already occupied (i.e., sol[i][j] ==
-1). We will make the value of all the unoccupied cells equal to -1.

IS-VALID(i, j, sol) {
if (i>=1 and i<=N and j>=1 and j<=N and sol[i][j]==-1) {
return TRUE
}
return FALSE
}

x_move = [2, 1, -1, -2, -2, -1,

1, 2]
y_move = [1, 2, 2, 1, -1, -2, -2,
-1]
Knights Tour Problem-Algorithm
Knights Tour Problem-Algorithm
Knights Tour Problem
Time Complexity

• The reason for this is that the knight’s tour problem as

we have implemented it so far is an exponential
algorithm of size O(K^N), where N is the number of
squares on the chessboard, where k is a small constant.
• Best case : In any step no backtracking is found
necessary, then Time complexity is O(N), in an n*n
chessboard. (N is no of squares on chessboard).
 Travelling Salesman Problem (TSP)
• The Traveling Salesman Problem (TSP) is a
deceptively simple combinatorial
problem. It can be stated very simply:
• A salesman spends his time visiting n
cities (or nodes) cyclically. In one tour he
visits each city just once, and finishes up
where he started. In what order should
he visit them to minimize the distance
traveled?
Applications of TSP
• A postal van is to pick up mail from mail boxes located
at n different sites. The route taken by a postal van is a
tour and the problem is to find a tour of minimum
length.
• A minimum cost tour of a robot arm used to tighten the
nuts on some piece of machinery on an assembly line
will minimize the time needed for the arm to complete
its task
 Travelling Salesman Problem
• For example: Consider the graph shown in figure
on right side. A TSP tour in the graph is 1-2-4-3-1.
The cost of the tour is 10+25+30+15 which is 80

• Naïve Solution:
1) Consider city 1 as the starting and ending
point.
2) Generate all (n-1)! Permutation of cities.
3) Calculate cost of every permutation and keep
track of minimum cost permutation.
4) Return the permutation with minimum cost.

• Time Complexity: O(n!)

TSP Backtracking Approach
• The TSP Backtracking solution could be formulated in two steps-

Step 1: Finding out all possible Hamiltonian cycle in the Graph (having n vertices
which represents n cities) using backtracking approach.
Step 2: Finally, find out the Minimum cost Hamiltonian cycle among all other
Hamiltonian cycles.
Finding all Hamiltonian Cycles using
Backtracking Approach
Check Hamiltonian cycles (manually) in the following Graph:
a
a b
b e c b
e c a d
d
Pendant Vertices
f
d c Junction point
a -> b -> c -> d -> e -> a
f e
a -> c -> d -> e -> b -> a
a -> b -> e -> d -> c -> a
.
.
 9
10
1 2
12 11
20
18
3
15 13
5 4 G is the adjacency matrix

X 1 2 3 4 5
X 1 2 5 4 3
[1] [2] [3] [4] [5]
[1] [2] [3] [4] [5]

1
2
3 4 5
4 3 5 4
5 3 https://www.youtube.com/watch?v=dQr4wZCiJJ4
 procedure Hamiltonian(k)
while(true) do
NextVertex(k)
if (X[k] == 0)
return
if (k == n)
print(X[1:n])
else
Hamiltonian(k+1)
endif
end while
end Hamiltonian

Time Complexity of backtracking approach:

(n-1) ! = O (n !)
No improvement as compared to Naïve Solution,
Travelling Salesman Problem (TSP)

• 0/1 Knapsack problem is a subset selection

problem. Given n objects there are 2n different
subsets of objects. The solution is one of these 2n
subsets.
• In permutation problems like Traveling
Salesperson Problem(TSP) there are n! different
permutations of n objects. (n!> 2n)
How Hard?
Number of possible tours:
N! = 1×2×3×⋅⋅⋅×(N-1)×N = Θ(2NlogN)
10! = 3,628,200
20! ~ 2.43×1018 (2.43 quadrillion)

Dynamic Programming Solution:

O(N22N)
102210 = 102,400
202220 = 419,430,400
Example
• Consider the directed graph
which has the adjacency
matrix as follows:

0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
• Consider the directed graph
which has the adjacency
matrix as follows:

0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
• Consider the directed graph
which has the adjacency
matrix as follows:

0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
Solving TSP by Dynamic
Programming
• Regard a tour to be a simple path that starts and end at vertex
1.
• Every tour consists of an edge <1,k> for some k ∈V – {1} and a
path from k to vertex 1. The path from vertex k to vertex 1
goes through each vertex in V – {1,k} exactly once.
• Let g(i, S) be the length of a shortest path starting at vertex i,
going through all vertices in S and terminating at vertex 1.
• g(1, V- {1}) is the length of an optimal salesperson tour.
• From the principle of optimality it follows that:
g(1, V – {1}) = min {c1k + g(k, V- {1, k})} (1)
2≤k ≤n
• Generalizing from (1) we obtain
g(i, S) = minj∈S {cij + g(j, S - {j})} (2)

• Formula (2) may be solved for g(1, V - {1}) if we know g(k, V -

{1,k}) for all choices of k.

• The g values may be obtained by using (2).

• Clearly, g(i, ∅) = ci,1, 1 ≤ i ≤ n. Hence, we may use (2) to obtain

g(i, S) for all S of size 1.
• Then we can obtain g(i, S) for S which |S| = 2.
• Then, we can obtain g(i, S) for S which |S| = 3, etc.
• When |S| < n -1, the value of i and S for which g(i, S) is needed
are such that i ≠ 1; 1∉S and i ∉S.
Example
• Consider the directed graph which has the adjacency matrix as follows:

0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

g(2, ∅) = c21 = 5 ; g(3, ∅) = c31 = 6; g(4, ∅) = c41 = 8.

Using (2) we obtain

g(2, {3}) = c23 + g(3, ∅) = 9 + 6 = 15
g(2, {4}) = c24 + g(4, ∅) = 10 + 8 = 18
g(3, {2}) = c32 + g(2, ∅) = 13 + 5 = 18
g(3, {4}) = c34 + g(4, ∅) = 12 + 8 = 20
g(4, {2}) = c42 + g(2, ∅) = 8 + 5 = 13
g(4, {3}) = c43 + g(3, ∅) = 9 + 6 =15
• Next, we compute g(i, S) with |S| = 2 and i ≠ 1; 1∉S and i ∉S.
g(2, {3,4})= min {c23 + g(3,{4}), c24 + g(4,{3})} = 25
g(3, {2,4})= min {c32 + g(2,{4}), c34 + g(4,{2})} = 25
g(4, {2,3})= min {c42 + g(2,{3}), c43 + g(3,{2})} = 23
• Finally, from (2) we obtain:
g(1, {2, 3,4})= min {c12 + g(2,{3, 4}), c13 + g(3,{2,4}), c14 + g(4,{2,3})} = min
{35, 40, 43} = 35
• An optimal tour of the graph has length 35.

• A tour of this length may be constructed if we retain with each g(i, S) the
value of j that minimizes the right hand side of (2). Let J(i, S) be this value.
• J(1, {2,3,4}) = 2. Thus the tour starts from 1 and goes to 2. The remaining
tour may be obtained from g(2, {3,4}). J(2, {3,4}) = 4. Thus the next edge is
<2,4>. The remaining tour is for g(4,{3}). J(4, {3}) = 3. The optimal tour is <1,
2, 4, 3, 1>
 Complexity of the method
• Let N be the number of g(i, S) that have to be computed before (1) may be
used to compute g(1, V – {1}). For each value of |S| there are n – 1 choices
for i. The number of distinct sets of sets S of size k not including 1 and i is
C(k, n -2).
n-2
• Hence N = Σ (n - 1) C(k, n - 2) = (n - 1)2n-2
k=0
• An algorithm that proceeds
2 n
to find an optimal tour by making use of (1) and
(2) will require O(n 2 ) time since the computation of g(i, S) with |S| = k
requires k -1 comparisons when solving (2).
• It’s better than enumerating all n! different tours to find the best one.

• The most serious drawback of this dynamic

n
programming solution is the
space needed. The space needed in O(n.2 ). This is too large even for
modest values of n.