Backtracking

Unit 6
Introduction

Backtracking is a general algorithmic technique for finding solutions

to some computational problems, notably constraint satisfaction
problems
Backtracking incrementally builds candidates to the solutions, and
abandons a candidate ("backtracks") as soon as it determines that
the candidate cannot possibly be completed to a valid solution
Many of the problems we solve using backtracking require that all
solutions satisfy a set of constraints

Prepared by Sherin Joshi

Introduction

Consider a situation that you have three boxes in front of you and
only one of them has a gold coin in it but you do not know which one
So, in order to get the coin, you will have to open all of the boxes one
by one
You will first check the first box, if it does not contain the coin, you
will have to close it and check the second box and so on until you
find the coin
This is what backtracking is, that is, solving all sub-problems one by
one in order to reach the best possible solution
Prepared by Sherin Joshi
Introduction

Example:
There are 5 tunnels and only one (or some) of them lead to an open
road on the other side whereas the others lead to a dead end
You start from tunnel 1 and explore it
If you reach a dead end, you backtrack and then check tunnel 2 and
so on
Prepared by Sherin Joshi
Introduction

Example:
In cryptarithmetic problems like SEND + MORE = MONEY, you
reach a stage like N is either 6 or 7
If you check for N = 6 and find out it cannot be the solution, you
backtrack and check for N = 7

Prepared by Sherin Joshi

Introduction

Backtracking explores all possible cases/scenarios and produces all

outputs that satisfy the given constraints
Dynamic Programming always only produces the optimal solution

Prepared by Sherin Joshi

Recursion VS Backtracking

Recursion is when a function calls itself until a base case is reached

Backtracking is when an algorithm makes an opportunistic decision,
which may come up to be wrong
If the decision was wrong, then the backtracking algorithm restores
the state before the decision
In backtracking you use recursion in order to explore all the
possibilities until you get the best result for the problem
Prepared by Sherin Joshi
Sum of Subsets

We are given ‘n’ distinct positive numbers wi, 1 ≤ i ≤ n (usually called

weights) and ‘m’
The sum of subsets problem is to find all subsets of wi whose sums
are m
For example, if n = 4, (w1, w2, w3, w4) = (11, 13, 24, 7), and m = 31,
then the desired subsets are (11, 13, 7) and (24, 7)

Prepared by Sherin Joshi

Sum of Subsets

We represent each solution subset by an n-tuple (x1, x2, .... , xn) such
that xi = {0, 1}, 1 ≤ i ≤ n
Then xi = 0 if wi is not chosen and xi = 1 if wi is chosen
The solutions of the given example are (1, 1, 0, 1) and (0, 0, 1, 1)
This formulation expresses all solutions using a fixed-sized tuple

Prepared by Sherin Joshi

Sum of Subsets

Eg: n = 6, m = 30, and w[1 : 6] = {5, 10, 12, 13, 15, 18}
(We assume wi’s are initially in nondecreasing order)

The solution space consists of 2n distinct tuples

Prepared by Sherin Joshi

State Space Tree:

(For a node at
level i, the left
child corresponds
to xi = 1 and the
right to xi = 0)
Prepared by Sherin Joshi
Bounding Functions

We will apply backtracking and kill nodes if they do not satisfy the
bounding functions:

Prepared by Sherin Joshi

Bounding Functions

Here,
(i = 1 to k) ∑wixi → sum of the weights included so far

(i = k+1 to n) ∑wi → sum of remaining weights

wk+1 → weight of the next object

Prepared by Sherin Joshi
Sum of Subsets

The next slide shows the state space tree for the given question with
bounding functions applied and when backtracking is used
The full state space tree for n = 6 contains 26 - 1 = 63 nodes from
which calls could be made (this count excludes the 64 leaf nodes as
no call need be made from a leaf)

Prepared by Sherin Joshi

Prepared by Sherin Joshi
Sum of Subsets

The given tree shows that we can obtain the sum m = 30 from three
subsets indicated by nodes labeled ‘A’, ‘B’ and ‘C’
The solutions are:
(1, 1, 0, 0, 1) [i.e. {5, 10, 15} ]
(1, 0, 1, 1) [i.e. {5, 12, 13} ]
(0, 0, 1, 0, 0, 1) [i.e. {12, 18} ]
Prepared by Sherin Joshi
Prepared by Sherin Joshi
Sum of Subsets

SumOfSub(s, k, r) → s - sum of weights included so far

k - checking for weight wk
r - sum of remaining weights
The initial call is SumOfSub(0, 1, ∑wi)
The time complexity of Sum of Subsets problem solved using
backtracking is O(2n)
Prepared by Sherin Joshi
0-1 Knapsack Problem

Given n positive weights wi , n positive profits pi , and a positive

number m that is the knapsack capacity, this problem calls for
choosing a subset of weights such that

The xi’s constitute a zero-one valued vector

Prepared by Sherin Joshi
0-1 Knapsack Problem

A good bounding function for this problem is obtained by using an

upper bound on the value of the best feasible solution obtainable by
expanding the given live node and any of its descendants
If the upper bound is not higher than the value of the best solution
determined so far, then that live node can be killed
If the items included up to a node have a greater total profit than the
best solution so far, we change the value of the best solution so far
Prepared by Sherin Joshi
0-1 Knapsack Problem

We always visit a promising node's children

A node is promising only if we should expand to its children
If at node Z the values of xi , 1 ≤ i ≤ k, have already been determined,
then an upper bound for Z can be obtained by relaxing the
requirement xi = 0 or 1 to 0 ≤ xi ≤ 1 for k+1 ≤ i ≤ n and using the
greedy algorithm to solve the relaxed problem

Prepared by Sherin Joshi

0-1 Knapsack Problem

Function Bound(cp, cw, k) determines an upper bound on the best

solution obtainable by expanding any node Z at level k+1 of the
state space tree
The object weights and profits are w[i] and p[i]
It is assumed that p[i]/w[i] > p[i+1]/w[i+1], 1 ≤ i ≤ n
We will only use greedy considerations to limit our search; we will
not develop a greedy algorithm
Prepared by Sherin Joshi
0-1 Knapsack Problem

To that end, we first order the items in non-increasing order

according to the values of pi/wi , where wi and pi are the weight and
profit, respectively, of the ith item
Suppose we are trying to determine whether a particular node is
promising
No matter how we choose the remaining items, we cannot obtain a
higher profit than we would obtain if we were allowed to use the
restrictions in the Fractional Knapsack problem from this node on
Prepared by Sherin Joshi
Prepared by Sherin Joshi
0-1 Knapsack Problem

From Bound it follows that the bound for a feasible left child of a
node Z is the same as that for Z
Hence, the bounding function need not be used whenever the
backtracking algorithm makes a move to the left child of a node
The resulting algorithm is BKnap

Prepared by Sherin Joshi

Prepared by Sherin Joshi
Prepared by Sherin Joshi
0-1 Knapsack Problem

Initially fp = -1
This algorithm is invoked as BKnap(1, 0, 0)

Prepared by Sherin Joshi

Example

The total profit, total weight, and bound are specified from top to
bottom at each node
Suppose that n = 4, m = 16, and we have the following:
i pi wi pi / w i
1 $40 2 $20
2 $30 5 $6
3 $50 10 $5
4 $10 5 $2
Prepared by Sherin Joshi
Example

Prepared by Sherin Joshi

Example

Hence, maximum obtainable profit = $90

Items included = {1, 3}

Time complexity of 0-1 Knapsack Problem using backtracking is

O(2n)

Prepared by Sherin Joshi

N-Queens Problem

Place ‘n’ queens on an n x n chessboard so that no two “attack”, i.e.,

so that no two of them are on the same row, column or diagonal
Since each queen must be on a different row, without the loss of
generality, assume queen ‘i’ is to be placed on row i
All solutions to the n-queens problem can be represented as
n-tuples (x1, x2, .... , xn), where xi is the column on which queen i is
placed
Prepared by Sherin Joshi
N-Queens Problem

The implicit constraints for this problem are that no two xi’s can be
the same (i.e., all queens must be on different columns) and no two
queens can be on the same diagonal
8-queens is the most commonly used n-queens problem

Prepared by Sherin Joshi

Example

Consider the n-queens problem for n = 4

Edges are labeled by possible values of xi
Edges from level 1 to level 2 nodes specify the values for x1
Edges from level i to level (i+1) are labeled with values of xi

Prepared by Sherin Joshi

Example

Permutation
Tree:

Prepared by Sherin Joshi

Example

Total nodes = 1 + 4 + (4 * 3) + (4 * 3 * 2) + (4 * 3 * 2 * 1)
=
= 65

Prepared by Sherin Joshi

Example
Total nodes (in n-queens state space tree)
=

There are n^2Cn possible ways in total (brute force)

eg: For 8x8 chessboard there are 64C8 possibilities to place 8 queens
However, by only allowing placement of queens on distinct rows and
columns, we require the examination of at most n! n-tuples
Prepared by Sherin Joshi
Example

Part of the
State Space
Tree when
Bounding
Function is
used and
problem is
solved using
backtracking
Prepared by Sherin Joshi
Example
Bounding Function = no same row, column or diagonal for multiple
queens
When we complete the tree, we get 2 solutions: (2, 4, 1, 3) and (3, 1,
4, 2)

Prepared by Sherin Joshi

Algorithm

We can observe that for every element on the same diagonal which
runs from the upper left to the lower right, each has the same “(row -
column)” value
Also, every element on the same diagonal which goes from the
upper right to the lower left has the same “(row + column)” value

Prepared by Sherin Joshi

Algorithm

Suppose two queens are placed at position (k, i) and (j, x[j])
Then, they are on the same diagonal only if
k - i = j - x[j] OR k + i = j + x[j]
From the 1st equation,
k - j = i - x[j]
From the 2nd equation,
i - x[j] = j - k
Prepared by Sherin Joshi
Algorithm

Therefore, two queens lie on the same diagonal if and only if

| i - x[j] | = | j - k |
OR, | x[j] - i | = | j - k |

Prepared by Sherin Joshi

Algorithm
Can a new queen be placed?

Prepared by Sherin Joshi

Algorithm

Prints all
solutions
to the
n-queens
problem

Prepared by Sherin Joshi

Algorithm

Here, k = number of the current queen that needs to be placed in

the chessboard

As we know, to place n queens in a nxn chessboard requires

checking of n! n-tuples
Hence, time complexity of the n-queens problem solved using
backtracking is O(n!)
Prepared by Sherin Joshi