What is Backtracking Algorithm?
To understand backtracking, consider an example:
Imagine, you want to go from one city to a different city through driving. Obviously, there will be many routes to your destination city and you will choose one of them.
Suppose in the way you find a road is undergoing construction or is closed. Now, what will you do?
Definitely, you will not go back straightaway to your home to take another route. You will go back to the last turn and will take another free road to continue your journey.
This process of going back a little and continuing with another valid path is known as Backtracking.
So Backtracking Algorithm is simply, going back one step if no further solution is possible and proceed with next available option.
Graphical Representation of Backtracking
Graphically, Backtracking is Depth First Search. Because depth-first search in general, make use of backtracking.
Watch the animation below, you will notice that on reaching the end (i.e leaf node), we go back upwards one step and if there is some child node unvisited we visit that node (i.e follow the new node’s path). We repeat this process until we visit all the nodes of the graph.
Note: Depth First Search means, first go to the depth along single path/branch unless no option is left, then come back by checking the chances of going forward at each step.
How to implement Backtracking?
Backtracking is implemented by using a stack.
In Backtracking, we require to go back on reaching a particular point or situation and thus we need to keep track of what we have processed in our last step. Therefore stack which follows LIFO (Last In First Out) pattern help in accomplishing the same.
And in order to implement stack we use Recursion. Because in Recursion, on reaching the base case the recursive function automatically starts going back to previous recursive call until it reaches to its first recursive call.
Thus in the process of going back, we explicitly manipulate recursive function so that it goes forward with a different option if available.
Therefore implementing BackTracking.
How to know When to Use Backtracking?
Anytime you solve a problem, that is solved by a series of decisions, you might make a wrong decision and when you realize that, you have to backtrack to a place where you made a decision and try something else.
Thus, break and analyze your given problem. If the series of decision needs to be made in the process to solve your problem, then there is a high chance, that the problem can be solved using Backtracking.
Example: N Queens Problem
In ‘N Queens Problem’, we require to make the decision at every chessboard cell, whether it is safe to place queen or not. If yes then we proceed to the next column for another queen, else we go back to decide another safe cell to place previously placed queen.
- Backtracking is often much faster then Brute Force method because it can eliminate large number of decisions with a single test.
- Backtracking is an important tool for solving constraint satisfaction problem.
- The Backtacking algorithm traverses the tree recusively from the root to down(DFS).
- Soduko can be solved using Backtracking
Implementation of Backtracking algorithm for different types problems can vary drastically. Hence writing general pseudocode for backtracking is not a wise move. First, understand the concept of backtracking and try to implement it with the use of recursion. Do check our different examples on backtracking algorithm here to know how to use Backtracking.