There are many Problem Solving Strategies like the Brute-force approach, dynamic programming approach, and recursive approach. One such strategy is the Backtracking approach. Backtracking can be defined as a strategy that, searches for every possible technique to solve a problem, abandoning a technique if it does not seem to give a feasible solution.
In this article, we will give an introduction to Backtracking.
What is Backtracking?
Backtracking is a problem-solving strategy for finding all the solutions to a problem, by rejecting the solutions that do not satisfy the given constraint. In Backtracking, we pick a path and start solving the problem along that path. At any point in time, if we find that the path is leading to an invalid solution, we stop moving along that path and return back to explore other paths.
Sample Example
We want to find different ways in which three shapes (a diamond, a square and a triangle) can be arranged in a sequence, given the triangle should never be in the middle.
All the possibilities are:
Diamond,Square, Triangle.
Square, Diamond, Triangle
Triangle, Diamond, Square
Triangle, Square, Diamond
The state space tree is shown below:
Say we choose the diamond to be the first in the sequence. We will have two options for the second place - a square and a triangle. If we choose the square as the second element then the third element will be the triangle. As this sequence obeys the constraint, we accept it as a valid solution. We cannot choose the triangle as the second element, so we abandon this solution.
In the above example, we backtrackedwhen we encountered a situation (the triangle as the second element) that did not satisfy our condition (the triangle should not be the middle element).
We can make some observations about Backtracking from the above example:
1️⃣ The problem must have a constraint.
2️⃣ The problem might have more than one solution.
Types of Backtracking
Backtracking tries to search each and every possible combination of solutions at each step to solve.
We have three different types of classic problems in backtracking, which are as follows:
Enumeration problems:- In these kinds of problems, we tend to find all the feasible solutions.
Decision problems:- In these kinds of problems, we tend to find one feasible solution.
Optimization problems:- In these kinds of problems, we tend to find the best-optimized solution
Pseudo Code for Backtracking
Recursive Code
void exploreSolutions(n, params) :
if (found a solution) :
totalSolutions = totalSolutions + 1;
displaySolution();
if (totalSolutions >= solutionTarget) :
System.exit(0);
return true;
for (val in array of possibilities) :
if (doesSatisfyConstraints(val, n, params)) :
appendValue(val, n);
bool result = exploreSolutions(n + 1, params);
if (result == false)
removeValue(val, n);
return false;
Finding whether a solution exists or not
boolean checkSolution(n, params) :
if (found a solution) :
displaySolution();
return true;
for (val in array of possibilities) :
if (doesSatisfyConstraints(val, n)) :
appendValue(val, n);
if (findSolutions(n+1, other params) is true)
return true;
removeValue(val, n);
return false;
Backtracking vs Brute-force Approach
Do not confuse Backtracking with the Brute-force approach. In the Brute-force approach, we explore all the options till the end, after which we check if the final answer is the desired solution. In Backtracking, we stop exploring an option mid-way if we find out that this option will not give a feasible solution. In Backtracking, we do not go all the way to the end to reject an option which saves us a lot of time.
Backtracking is often faster than the brute force approach as it does not require generating and testing all possible solutions. Instead, it can eliminate a large number of candidates with a single test.
For the Sudoku solving problem, we can use the brute force approach and generate all possible combinations of numbers and then try every combination one by one. This will be time-consuming. Instead, we can use Backtracking, we try each digit one by one and if we find that the digit cannot give a solution we backtrack by removing it and trying the next digit, which allows us to drop some of the permutations. Hence, Backtracking is better than Brute-force.
Backtracking vs Recursion
The process of exploring all the options is done via recursion but Backtracking is just a form of recursion. It is different from a Recursive Approach. In Recursion, until we reach a base case we keep calling the function. Whereas, in Backtracking, we keep exploring the options until the best solution is obtained.
You can use Backtracking if there is a constraint that determines the outcome or if you want to find all of the possible outcomes of a problem. It can also be used to solve some optimization problems in which we abandon an option as soon as we determine, it does not lead to a solution.
A classic problem to understand Backtracking is the N-Queens problem. We recommend you to go through it.
If you want to read more articles we recommend you these articles:
Backtracking is a problem-solving strategy for finding all the solutions to a problem, by rejecting the solutions that do not satisfy the given constraint
Is backtracking DFS or bfs?
Backtracking is a problem-solving algorithm that incrementally builds solutions and abandons them if they fail to satisfy constraints. It is more closely related to Depth-First Search (DFS) because it explores one path fully before backtracking to try another.
What is backtracking in automata?
In automata, backtracking involves revisiting previous states to explore alternative paths when the current path fails to satisfy the desired conditions, often used in pattern matching and parsing.
Conclusion
In this article, we discussed what backtracking is with the help of an example. We also discussed how backtracking is different from brute force and recursion.
Now, that we have understood what Backtracking is, we encourage you to solve some of the backtracking problems.
117+ registered 