Backtracking
Backtracking is a systematic way of trying out different sequences of decisions until we find
one that "works." A backtracking algorithm tries to construct a solution to a computational
problem incrementally, one small piece at a time. Whenever the algorithm needs to decide
between multiple alternatives to the next component of the solution, it recursively evaluates
every alternative and then chooses the best one.
Backtracking algorithm is applied to some specific types of problems,
Decision problem used to find a feasible solution of the problem.
Optimisation problem used to find the best solution that can be applied.
Enumeration problem used to find the set of all feasible solutions of the problem.
In backtracking problem, the algorithm tries to find a sequence path to the solution which has
some small checkpoints from where the problem can backtrack if no feasible solution is found
for the problem.
Algorithm
Step 1 − if current_position is goal, return success
Step 2 − else,
Step 3 − if current_position is an end point, return failed.
Step 4 − else, if current_position is not end point, explore and repeat above steps.
Example1:
backtracking problem to find the solution to N-Queen Problem.
In N-Queen problem, we are given an NxN chessboard and we have to place n queens on the
board in such a way that no two queens attack each other. A queen will attack another queen if it
is placed in horizontal, vertical or diagonal points in its way. Here, we will do 4-Queen problem.
Here, the solution is −
Here, the binary output for n queen problem with 1’s as
queens to the positions are placed.
{0 , 1 , 0 , 0}
{0 , 0 , 0 , 1}
{1 , 0 , 0 , 0}
{0 , 0 , 1 , 0}
For solving n queens problem, we will try placing queen
into different positions of one row. And checks if it
clashes with other queens. If current positioning of queens
if there are any two queens attacking each other. If they
are attacking, we will backtrack to previous location of the queen and change its positions. And
check clash of queen again.
Example 2: Hamiltonian Circuit Problems
Given a graph G = (V, E) we have to find the Hamiltonian Circuit using Backtracking approach.
We start our search from any arbitrary vertex say 'a.' This 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.
Consider a graph G = (V, E) shown in fig. we have to find a Hamiltonian circuit using
Backtracking method.
Solution: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our
implicit tree.
Next, we choose vertex 'b' adjacent to 'a' as it comes first in lexicographical
order (b, c, d).
Next, we select 'c' adjacent to 'b.'
Next, we select vertex 'f' adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have already
visited. Thus, we get the dead end, and we backtrack one step and remove the vertex 'f' from
partial solution.
From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already
been checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex
adjacent to d are e, f from which e has already been checked, and adjacent of 'f' are d and e. If 'e'
vertex, revisited them we get a dead state. So again we backtrack one step.
Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a.'
Here, we get the Hamiltonian Cycle as all the vertex other than the start vertex 'a' is visited only
once. (a - b - c - e - f -d - a).
Example3 : 0/1 Knapsack problem with Backtracking
Given a Knapsack of capacity W=8.
i 1 2 3 4
wi 2 3 4 5
pi 3 5 6 10
Which items can be added in knapsack to fill it to maximum while earning
maximum profit? Solve using Backtrack Methos.
