Backtracking

• One of the problem-solving strategy

• Uses brute force approach
– It tries all possibilities and comes out with the
desired solution
• Not for optimization problems
• Suits to the scenario when multiple solutions
are there and need all those solutions
• Suits to CSP (constraint satisfaction problems )
• A method to solve problems by making series
of choices that we can return or backtrack to.
Definition
• finding all (or some) solutions to some
computational problems, notably constraint
satisfaction problems, that 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.
• can be applied only for problems which admit
the concept of a "partial candidate solution"
and a relatively quick test of whether it can
possibly be completed to a valid solution
• constraint satisfaction problems such as
• crosswords,
• verbal arithmetic,
• Sudoku, and many other puzzles
• finding a path in a maze puzzle
• assembling lego pieces
Working methodology
• The backtracking algorithm traverses this search
tree recursively, from the root down, in depth-
first order.
• At each node c, the algorithm checks whether c
can be completed to a valid solution. If it cannot,
the whole sub-tree rooted at c is skipped
(pruned). Otherwise, the algorithm
(1) checks whether c itself is a valid solution, and
if so reports it to the user; and
(2) recursively enumerates all sub-trees of c.
Comparison
• Both are based on the construction of a state-
space tree whose nodes reflect specific choices
made for a solution’s components.
• Both techniques terminate a node as soon as it
can be guaranteed that no solution to the
problem can be obtained by considering choices
that correspond to the node’s descendants. The
techniques differ in the nature of problems they
can be applied to.
Nature of the problem
• There are problems that are difficult to solve
algorithmically.
• Unlike exhaustive search, they construct
candidate solutions one component at a time
and evaluate the partially constructed
solutions: if no potential values of the
remaining components can lead to a solution,
the remaining components are not generated
at all.
Backtracking
The principal idea is to construct solutions one
component at a time and evaluate such partially
constructed candidates as follows.
• If a partially constructed solution can be developed
further without violating the problem’s constraints, it
is done by taking the first remaining legitimate option
for the next component.
• If there is no legitimate option for the next
component, no alternatives for any remaining
component need to be considered. In this case, the
algorithm backtracks to replace the last component of
the partially constructed solution with its next option.
State space tree
• constructing a tree of choices being made, called the
state-space tree. Its root represents an initial state
before the search for a solution begins.
• The nodes of the first level in the tree represent the
choices made for the first component of a solution,
• the nodes of the second level represent the choices for
the second component, and so on.
• A node in a state-space tree is said to be promising if
it corresponds to a partially constructed solution that
may still lead to a complete solution; otherwise it is
called nonpromising.
• Leaves represent either non promising dead
ends or complete solutions found by the
algorithm. In the majority of cases, a state
space
• tree for a backtracking algorithm is
constructed in the manner of depth first
search.
Backtracking (animation)

dead end
?
dead end
dead end
?
start ? ? dead end
dead end
?
success!

12
Terminology I
A tree is composed of nodes

There are three kinds of

nodes:
The (one) root node
Backtracking can be thought of
Internal nodes
as searching a tree for a
Leaf nodes particular “goal” leaf node
13
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
parent the root at the top
children children

14
• N-Queens problem – permutations with
backtracking
• Hamiltonian circuit problem
• Sub set sum problem
• Soduko – counting with backtracking
• Scheduling – subsets with backtracking
N-Queens problem

The problem is to place n queens on an n × n chessboard so that no two

queens attack each other by being in the same row or in the same column
or on the same diagonal
• How can N queens be placed on an NxN
chessboard so that no two of them attack
each other?
State Space tree

Solution :
2 4 13
3142
N queens -Algorithm
1) Start in the leftmost column
2) If all queens are placed
return true
3) Try all rows in the current column.
Do following for every tried row.
a) If the queen can be placed safely in this row then mark this [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 lead to a solution then unmark this [row, column]
(Backtrack) and go to step (a) to try other rows.
3) If all rows have been tried and nothing worked, return false to trigger
backtracking.

The time complexity is O(n^2) because we are selecting if we can put

or not put a Queen at that place.
Hamilton Path
• Find a simple path that visits every vertex
exactly once.
• Backtracking solution. To find Hamilton path
starting at v:
• Add v to current path.
• For each vertex w adjacent to v
• find a simple path starting at w using all remaining
vertices
• Remove v from current path.
It is a special type of TSP (Travelling salesman
Problem)
Hamiltonian Circuit Problem

• Time Complexity for finding the Hamiltonian Cycle using the Backtracking
approach is O(N!), where N is the number of vertices in the graph.
Hamiltonian Circuit Problem
Hamiltonian Circuit Problem

Kindly add the remaining branch

Sub set sum Problem
• Find a subset of a given set A = {a1, . . . , an} of
n positive integers whose sum is equal to a
given positive integer d.
• For example, for A = {1, 2, 5, 6, 8} and d = 9,
there are two solutions:
• {1, 2, 6} and {1, 8}.
subset Sum problem using a backtracking approach which will take O(2^N) time
complexity but is significantly faster than the recursive approach which take
exponential time as well.
State space tree
A={3,5,6,7}
d=15
Let s, the sum of these numbers, in the node.
If s is equal to d, we have a solution to the
problem.
We can either report this result and stop or, if
all the solutions need to be found, continue by
backtracking to the node’s parent.
• If s is not equal to d, we can terminate the
node as nonpromising if either of the following
two inequalities holds:
Differences
Backtracking Branch and Bound
applicable only to non-optimization applicable only to optimization
problems. problems because it is based on
computing a bound on possible
values of the problem’s objective
function
can generate nodes according to the can generate nodes according
order (DFS)in which nodes of the to several rules: the most natural
state-space tree are generated one is the so-called best-first rule

Follows DFS Follows BFS

Tutorial
• When 3X3 CHESSBOARD is given, how 3
queens can be placed without attacking each
other? Construct a state space tree for the
above given problem.