BACKTRACKING
Introduction
A backtracking algorithm is a problem solving algorithm that uses a brute force approach for finding the
desired output.
The Brute force approach tries out all the possible solutions and chooses the desired/best solutions.
The term backtracking suggests that if the current solution is not suitable, then backtrack and try other
solutions. Thus, recursion is used in this approach.
This approach is used to solve problems that have multiple solutions.
State Space Tree
A space state tree is a tree representing all the possible states (solution or nonsolution) of the problem from the root
as an initial state to the leaf as a terminal state.
By Dr. Deep Suman Dev DAA – Backtracking [1]
Backtracking Algorithm Applications
To find all Hamiltonian Paths present in a graph.
To solve the N Queen problem
m Coloring Problem
Hamiltonian Cycle
In an undirected graph, the Hamiltonian path is a path, that visits each vertex exactly once, and the
Hamiltonian cycle or circuit is a Hamiltonian path, that there is an edge from the last vertex to the first vertex.
The starting vertex 'a' becomes the root of our implicit tree. The first element of our partial solution is the
first intermediate vertex of the Hamiltonian Cycle that is to be constructed. The next adjacent vertex is
selected by alphabetical order. If at any stage any arbitrary vertex makes a cycle with any vertex other than
vertex 'a' then we say that dead end is reached. In this case, we backtrack one step, and again the search
begins by selecting another vertex and backtrack the element from the partial; solution must be removed.
The search using backtracking is successful if a Hamiltonian Cycle is obtained.
Time complexity of the algorithm is O(2n N 2).
By Dr. Deep Suman Dev DAA – Backtracking [2]
By Dr. Deep Suman Dev DAA – Backtracking [3]
By Dr. Deep Suman Dev DAA – Backtracking [4]
M Coloring Problem
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 there exists a solution, then display which color is assigned on which vertex.
By Dr. Deep Suman Dev DAA – Backtracking [5]
Starting from the vertex 0, we will try to assign colors one by one to all the different nodes. But before
assigning, we have to check whether the color is safe or not. A color is not safe if the adjacent vertices are
containing the same color.
M Coloring Problem Backtracking Algorithm Flowchart
By Dr. Deep Suman Dev DAA – Backtracking [6]
By Dr. Deep Suman Dev DAA – Backtracking [7]
N-Queens Problem
N queens problem is one of the most common examples of backtracking.
Our goal is to arrange N queens on an NxN chessboard such that no queen can strike down any other queen.
A queen can attack horizontally, vertically, or diagonally.
So, we start by placing the first queen anywhere arbitrarily and then place the next queen in any of the safe
places.
We continue this process until the number of unplaced queens becomes zero (a solution is found) or no safe
place is left.
If no safe place is left, then we change the position of the previously placed queen.
Using Backtracking to Solve 4 Queens
By Dr. Deep Suman Dev DAA – Backtracking [8]
4 Queens solution space with nodes numbered in DFS
By Dr. Deep Suman Dev DAA – Backtracking [9]
One possible solution for 8 queens problem is shown in fig:
By Dr. Deep Suman Dev DAA – Backtracking [10]
By Dr. Deep Suman Dev DAA – Backtracking [11]
By Dr. Deep Suman Dev DAA – Backtracking [12]