Module 3-Part I
Backtracking
[Link] Choudhari
Backtracking
1. Backtracking is an algorithmic technique whose goal
is to use brute force to find all solutions to a
problem
2. To represent solution it uses State Space Tree.
9/26/2025 2
Example Backtracking Approach
Problem: We want to find all the possible ways of arranging 2 boys and 1
girl on 3 benches.
Solution: There are a total of 3! = 6 possibilities.
We will try all the possibilities and get the possible solutions.
We recursively try all the possibilities.
9/26/2025 3
State Space Tree for example
B1
B2
G
B2 B2 G
G B1 B1
G B2 B2 B1 B2 B1
9/26/2025 4
Backtracking Approach to solve the
example
Constraint: Girl should not be on the middle bench.
B1
B2
G Bounding
function
B2 B2 G
G B1 B1
G X B2 B1 G X
9/26/2025 5
Backtracking Approach to solve the
example Constraint: Girl should not be on the middle bench.
Backtracking uses DFS approach to
B1
B2 explore the node
G
B2 B2 G
G B1 B1
G X B2 B1 G X
9/26/2025 6
Branch and Bound Approach to solve the
example
Constraint: Girl should not be on the middle bench.
B1
B2 Uses BFS approach to
G
explore the node
B2 B2 G
G B1 B1
G X B2 B1 G X
9/26/2025 7
Backtracking- Rat on Maze
9/26/2025 8
Backtracking principle
Backtracking is a general algorithm for solving some computational problems,
most notably constraint satisfaction problems, that incrementally builds
candidates to the solutions and abandons a candidate as soon as it determines that
the candidate cannot be completed to a reasonable solution.
9/26/2025 9
Backtracking principle
• Backtracking find all answer nodes, not just one case.
• Let (x1... xi) be a path from root to a node in the state space tree.
• T(x1... xi) be the set of all possible values for xi+1 such that (x1,..., xi,xi+1) is also a path
to problem state.
• Let Bi+1 be a bounding function such that if Bi+1(x1, xi,xi+1) is false for the path (x1,
..., xi,xi+1) from the root to the problem state, then path cannot be extended to answer
node.
• Then candidates for position i+1 are those generated by the T satisfying Bi+1.
9/26/2025 10
Control Abstraction for backtracking
• Control abstraction for backtracking defines the flow of how it solves the
given problem in an abstract way.
• In backtracking, solution is defined as n-tuple X = (x1, x2, …, xn),
where xi = 0 or 1. xi is chosen from set of finite components Si.
If component xi is selected then set xi = 1 else set it to 0.
• Backtracking approach tries to find the vector X such that it maximize or
minimize certain criterion function P(x1, x2, …, xn).
9/26/2025 11
Control Abstraction for Recursive
Backtracking do
if
(Bk(x[1], x[2], …, x[k])) == TRUE
then
REC_BACKTRACK(k) // (Feasible solution)
if
// X[1…k – 1] is the solution vector (x[1], x[2], …, x[k]) is path to answer node
then
// T(x[1], x[2],…, x[K - 1]) is the state print (x[1], x[2], …, x[k])
space tree end
if
// Bk( ) is the bounding function k<n
then
for REC_BACKTRACK(k + 1)
each x[k] ∈ T[x[1], x[2], …, x[k – 1]] end
end
end
9/26/2025 12
Time analysis for backtracking
The performance of backtracking algorithm depends on four parameters:
1. Time to compute the tuple x[k] i.e. next x[k]
2. Number of x[k] which satisfy the explicit constraint
3. Time taken by bounding function Bk to generate a feasible sequence
4. A number of x[k] which satisfies the bounding function Bk for all k.
9/26/2025 13
Popular problems solved using backtracking
• N-Queen problem
• Sum of subset problem
• Graph coloring problem
• Knapsack problem
• Hamiltonian cycle problem
9/26/2025 14
N-Queen Problem
N - Queens problem is to place n - queens in such a manner on an n x n
chessboard that no queens attack each other by being in the same row,
column or diagonal.
Note: It can be seen that for n =1, the problem has a trivial solution, and no solution
exists for n =2 and n =3. So first we will consider the 4 queens problem and then
generate it to n - queens problem.
9/26/2025 15
4 Queen Problem
Given a 4 x 4 chessboard and number the rows and column of the chessboard
1 through 4 Explicit Constraints:
Explicit constraints are the rules that allow/disallow selection of
xi to take value from the given set.
Ex: For n-queen problem explicit constraint is Si={1,2,3,…,n}
1<=i<=n
Implicit constraints:
The implicit constraint is to determine which of the tuple of
solution space satisfies the given criterion functions. The implicit
constraint for n queen problem is that two queens must not appear
in the same row, column or diagonal.
9/26/2025 16
State Space Tree for
4-Queen Problem
9/26/2025 17
Backtracking procedure of
4-Queen problem
solution (2, 4, 1, 3)
4 queens problem can be represented
as 4 - tuples (x1, x2, x3, x4) where xi
represents the column on which queen
"qi" is placed.
9/26/2025 18
Attacked cells by queen Q
Cells on diagonal 1(d1): (1,0),(3,2)
0 1 2 3
Cells on diagonal 2 (d2): (3,0),(1,2),(0,3)
0 d2
Two elements (i,j) and (k,l) on Two elements (i,j) and (k,l) on
1 diagonal d1 have following diagonal d2 have following
relation relation
2
i-j=k-l i+j=k+l
d1
3
i.e. j-l= i-k i.e r1-r2=c1-c2…. 1 i.e. j-l= i-k i.e r1-r2=c1-c2…. 2
From equation 1 and 2 we can write
|j-l| = |i-k| or |c1-c2| = |r1-r2|
9/26/2025 19
One possible solution for 8 queens problem
• 8 queen problem has 64C =
8 4,42,61,65,368
different arrangements.
• Of these, only 92 arrangements are valid
solutions.
• Out of which, only 12 are the fundamental
solutions.
Solution tuple for the solution shown in fig is
• The remaining 80 solutions can be generated
defined as <4, 6, 8, 2, 7, 1, 3, 5>
using reflection and rotation
9/26/2025 20
Algorithm for n-Queen
N - Queens (k, n)
{ Place (k, i)
For i ← 1 to n {
do if Place (k, i) then For j ← 1 to k - 1
{ do if (x [j] = i)
x [k] ← i;
or (Abs x [j]) - i) = (Abs (j - k))
if (k ==n) then
then return false;
write (x [1....n]);
return true;
else
N - Queens (k + 1, n);
}
}
}
9/26/2025 21
Complexity Analysis
• In backtracking, at each level branching factor decreases by 1 and it
creates a new problem of size (n – 1) .
• With n choices, it creates n different problems of size (n – 1) at level 1.
• PLACE function determines the position of the queen in O(n) time.
This function is called n times.
• Thus, the recurrence of n-Queen problem is defined as,
T(n) = n*T(n – 1) + n2. Solution to recurrence would be O(n!).
9/26/2025 22
Graph Coloring problem
Input
• In this problem, an undirected graph is given. There is
also provided m colors. The problem is to find if it is
possible to assign nodes with m different colors, such
that no two adjacent vertices of the graph are of the
same colors.
• If the solution exists, then display which color is
assigned on which vertex.
9/26/2025 23
Input and Output
Input
Output
This algorithm will return which node will be assigned with
which color. If the solution is not possible, it will return false.
For this input the assigned colors are:
Node 0 -> color 1
Let the maximum color m = 3.
Node 1 -> color 2
Node 2 -> color 3
Node 3 -> color 2
9/26/2025 24
Algorithm 1
isValid(vertex, colorList, col)
Input − Vertex v, colorList to check, and color, which is trying to assign.
Output − True if the color assigning is valid, otherwise false.
Begin
for all vertices i of the graph, do
if there is an edge between v and i, and col = colorList[i], then
return false
done
return true
End
9/26/2025 25
Algorithm 2
graphColoring(colors, colorList, vertex)
Input − Most possible colors, the list for which vertices are colored with which color, and the starting vertex.
Output − True, when colors are assigned, otherwise false.
Begin
if all vertices are checked, then
return true
for all colors col from available colors, do
if isValid(vertex, colorList, col), then
add col to the colorList for vertex
if graphColoring(colors, colorList, vertex+1) = true, then
continue
remove color for vertex
done
return false
End
9/26/2025 26
Exercise
Find the solution for following graph for exactly 3 colours
9/26/2025 27
Time Complexity
• Since backtracking is also a kind of brute force approach, there would
be total O(mV) possible color combinations.
• It is to be noted that the upperbound time complexity remains the same
but the average time taken will be less due to the refined approach.
9/26/2025 28
Thank You!!
9/26/2025 29