Backtracking

Connecting the dots… Part 1

 4/26/2023
Introduction
• Desired solution is expressed as an n-tuple e.g. (X1, X2, …, Xn).

Preetam K Sur, Assistant Professor, Computer Science & Engineering

• Xi’s are chosen from a set of finite options, say Si.
• Suppose, set Si contains Mi numbers of elements.
• Then there are M = M1.M2…Mn numbers of possible solution candidates.
• Brute force approach eventually generates all the M solution candidates.
• Backtracking builds the solution vector one item at a time.
Then, evaluate whether the partial vector being formed can lead to a solution using a

Department, GCETTS
•
bounding function.
• Backtracking abandons the formed partial vector as soon as it found this vector
cannot lead to a solution, unlike Brute force approach.
• One solution vs. All solutions.
2
 •
Introduction

Si = { 0, 1 }
Si = { All non-negative real numbers }

Preetam K Sur, Assistant Professor, Computer Science & Engineering

4/26/2023
3

Department, GCETTS
 Illustration of Backtracking design technique – Part 2
n-Queens Problem

Preetam K Sur, Assistant Professor, Computer Science

4/26/2023
4

& Engineering Department, GCETTS

 4/26/2023
8-Queens Problem
1 2 3 4

Preetam K Sur, Assistant Professor, Computer Science & Engineering

1
Who do you think be an apt king to
2 manage his 8-queens?
3
4
5
5 6 7 8
6
Simplifying the the solution as –
So we can write
7 Problem
(4, 6, 8, 2, 7, 1, 3, 5)

Department, GCETTS
8 Can there be any other solution?
1 2 3 4 5 6 7 8
Representing the Problem
Since all the queens has to be in different row, we’ll assume the i-th queen is placed at i-th row.
Then the solution can be represent as 8-tuple as (X1, X2, …, X8), Xi denoting the column i-th
queen being placed.
5
 4/26/2023
Analyzing Problem
• What is the Explicit Constraints for 8-Queens Problem?

Preetam K Sur, Assistant Professor, Computer Science & Engineering

● i-th queen has to be placed in one of the 8 columns.
● 1 ≤ Xi ≤8
● Si = { 1, 2, 3, 4, 5, 6, 7, 8 }
● Total solution space consist 88 solution vectors.

• What is the Implicit Constraints for 8-Queens Problem?

● No two queens can be in the same column.
● No two Xi can have same value in a solution vector.
● This means all the solution vector is a permutation of values {1, 2, 3, 4, 5, 6, 7, 8}

Department, GCETTS
● Total solution space is now reduced to 8! from 88 solution vectors.

• Generalization : n-Queens Problem.

● 4-queens

6
 Solving 4-queens Problem

Preetam K Sur, Assistant Professor, Computer Science & Engineering

4/26/2023
7

Department, GCETTS
 How backtracking works – Part 3
The Mechanism

Preetam K Sur, Assistant Professor, Computer Science

4/26/2023
8

& Engineering Department, GCETTS

 4/26/2023
State Space Tree
• Tree organization of the solution space.

Preetam K Sur, Assistant Professor, Computer Science & Engineering

All path from
Each node root to other
in the tree nodes

Problem
State Space
State
Solution
Problemstates
states
that
formeets
whichthe
path
implicit
from root
constraints
to the node
of the
defines
problem
a tuple
Solution Answer
States States

Department, GCETTS
Solution Space for 4-Queen Problem

9
 4/26/2023
Generating Problem states
• Terminologies

Preetam K Sur, Assistant Professor, Computer Science & Engineering

● Live Node: A node which is generated, but all of its children are yet not generated.
● E-node: A live node whose children are currently being generated.
● Dead Node: A generated node which is not going to be expanded further.

• Two ways of generating the problem states.

• First Method:
● Suppose, a node P is currently E-node and it generates a new node C.
● As soon as the C node is generated, it becomes the new E-node.
● P will be E-node again when C becomes a dead node.

Department, GCETTS
● Depth first way, known as Backtracking.

• Second Method :
● An E-node remains E-node until it becomes dead.
● Breadth first way, known as Branch and Bound.

10
 4/26/2023
Generalized Backtracking
• Finding just one answer state, not all.

Preetam K Sur, Assistant Professor, Computer Science & Engineering

• Let (X1, X2, …, Xi) be a path from the root to a node in the state space tree.
• Let T(X1, X2, …, Xi) be the set of all possible values for Xi+1 such that (X1, X2, …, Xi+1)
is also a valid path to a problem state.
● Therefore, T(X1, X2, …, Xn) = ϕ

• Let B(X1, X2, …, Xi) be the bounding function.

● Returns false if the path (X1, X2, …, Xi) cannot be extended to an answer node.
● Returns true, if the path can be extended to an answer node.

Department, GCETTS
• With the help of these, we will define a generalized backtracking algorithm
• The initial call should be Backtrack(1)

11
 4/26/2023
Generalized Backtracking Algorithm
Algorithm : Backtrack(x, k, n)

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Input : x being the array representing the solution vector. k
denotes next value to be generated. n is the size of solution
vector.
Assumption : x[1..k-1] is assigned with valid values.
Output : Solution vector x populated with k-th valid value.
Begin
foreach x[k] ϵ T(x[1], …,x[k-1])
do
if B(x[1], …, x[k]) ≠ 0
then
if k < n

Department, GCETTS
then
return Backtrack(x, k+1, n)
else
return x
endif
endif
endfor
End 12
 The algorithms – Part 4
Solving n-Queens

Preetam K Sur, Assistant Professor, Computer Science

4/26/2023
& Engineering Department, GCETTS
13
 4/26/2023
Bounding Function : Place
Algortihm : Place (X[], k, i)

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Input : Solution vector X whose first k-1 values have been set. Row
number k. Column number i.
Output : True if a queen can be placed at k-th row, i-th column.
False, otherwise.
Begin
for j ← 1 to k – 1
do
if x[j] = i or |x[j] - i| = |j - k|
then

Department, GCETTS
return false
endif
endfor
return true
End
14
 4/26/2023
Algorithm : N-queens
Algortihm : NQueens(X[], k, n)

Preetam K Sur, Assistant Professor, Computer Science & Engineering

Input : Solution vector X, initially empty. Row number k, initially 1.
Number of queens n.
Output : X filled up with proper column numbers if possible; NIL if
impossible.
Begin
y ← NIL
for i ← 1 to n
do
if Place( X, k, i)
then
X[k] ← i

Department, GCETTS
if k = n then return X endif
y ← NQueens(X, k+1, n)
if y ≠ NIL then break endif
endif
endfor
return y
End
15
 Problem
Graph Coloring
Illustration of Backtracking designing techniques – Part 5

Preetam K Sur, Assistant Professor, Computer Science

4/26/2023
& Engineering Department, GCETTS
16
 Preetam K Sur, Assistant Professor, Computer Science
4/26/2023
& Engineering Department, GCETTS
17
 4/26/2023
Problem Description
• Given a graph G = (V, E).
• And, an integer m denoting the number of colors available.
• We need to tell whether the graph can be colored with only m colors and such that no

Preetam K Sur, Assistant Professor, Computer Science

two adjacent nodes have same color.
• m-colorability Decision Problem.

& Engineering Department, GCETTS

• m-colorability Optimization Problem
● Find out the smallest integer m for which the graph can be colored such that no two
adjacent nodes have same color.
● NP problem.
● Chromatic number

• Example
● Is it 2-colorable?
● Is it 3-colorable?
18
 4/26/2023
Graph Theory
• In computer science, graph can be represented in two ways –
● Adjacency List Representation.
● Adjacency Matrix Representation

Preetam K Sur, Assistant Professor, Computer Science

● A n x n matrix, G[1..n, 1..n], n being number of vertices of the graph
● G[i, j] = 1, if (i, j) is an edge between vertices i and j.
● G[i, j] = 0, otherwise.

& Engineering Department, GCETTS

• A graph with degree d can be surely coloured d+1 colors.
• A graphis planner iff it can be drawn in a plane such that no two
edges cross each other.
● For planner graph, 4 colours are sufficient.
● Any Map can be represented as a planner graph.

19
 The algorithms – Part 6
Coloring
Solving Graph

Preetam K Sur, Assistant Professor, Computer Science

4/26/2023
& Engineering Department, GCETTS
20
 4/26/2023
Solution Approach
• Sincem is the number of colors, let, the color be represented by
integers 1, 2, …, m.
• The solution can be given as n-tuples (X1, X2, …, Xn), where Xi denotes

Preetam K Sur, Assistant Professor, Computer Science

the color of node i.
• Explicit constraints: 1 ≤ Xi ≤ m.

& Engineering Department, GCETTS

● Search space : mn.

• So, the state space tree has degree m and height n+1.
● Each node at level i has m children corresponding to m possible assignment at Xi.
● Nodes at level n+1 are the leaf nodes representing the solution states of the
problem.

• Implicit constraints: Xi ≠ Xj, if (i, j) ϵ E, or, G[i, j] = 1.

21
 4/26/2023
Bounding Function: NextValue
Algorithm : NextValue(G, X, k, m)
Input : Adjacency Matrix G. Array X, X[i] = color of i-th vertex. Finding a
color for vertex k in range [0,m]. Highest m colors can be used.
Assumption : X[1…k-1] is populated with valid values. X[k…n] are all 0.
Output : X[k] will be assigned a valid color, if found. 0, if not found.

Preetam K Sur, Assistant Professor, Computer Science

Begin
while true
do

& Engineering Department, GCETTS

X[k] ← (X[k]+1) % (m+1)
if X[k] = 0 then return endif
for j ← 1 to k-1
do
if X[k] = X[j] and G[k, j] ≠ 0
then break endif
endfor
if j = k then return endif
endwhile
End
22
 4/26/2023
Algorithm : mColoring
Algorithm : mColoring ( G, X, k, m, n)
Input : Boolean adjacency matrix G. Array X, X[i] = color of i-th vertex,
initialized with 0. k is the next vertex to be colored. Highest m colors
can be used. Number of nodes n.
Output : NIL if not m-coloring. Otherwise, Array X where X[i] denotes the

Preetam K Sur, Assistant Professor, Computer Science

assigned color of i-th vertex.
Begin
while true

& Engineering Department, GCETTS

do
NextValue(G, X, k, m)
if X[k] = 0 then return NIL endif
if k = n then return X
else return mColoring (G, X, k+1, m, n)
endif
endwhile
End

23
 Connecting the Dots…

Preetam K Sur, Assistant Professor, Computer Science & Engineering

4/26/2023
Department, GCETTS
24
 Thank You!

Preetam K Sur, Assistant Professor, Computer Science & Engineering

4/26/2023
Department, GCETTS
25