When to use Backtracking Approach in Algorithms?
What is Backtracking?
For any given problem — be it a decision-making problem like whether to stop the vehicle at any instance — in autonomous driving, an optimization problem like choosing the best path from my home to the office, or an enumeration problem like generating all possible permutations and combinations of teams play-outs in a tournament.
For a computer, we need to give instructions to solve any problem (algorithm). We have different ways to solve a problem and hence different algorithmic patterns to solve problems. The basic and easy-to-program is the brute-force method, where we list all possible options/solutions and remove all unwanted ones.
Let us focus on one of the brute-force ways of solving a problem called Backtracking. Backtracking came from how we chose to arrive at the solution. It uses a recursive approach to find a feasible solution by building a solution incrementally with time and removing the options that don’t lead to a possible solution for the problem based on the constraints given.
According to the wiki definition, Backtracking is a general algorithmic technique that considers searching every possible combination to solve a computational problem.
We typically use backtracking to solve three types of problems.
- Decision Problem: We search for a feasible solution from the pool of all possible solutions.
- Optimization Problem: We search for the best solution.
- Enumeration Problem: We generate all possible solutions.
For a 7-year-old kid?
Consider a situation in which you have three boxes in front of you, and only one of them has a gold coin, but you do not know which one. So, to get the coin, you will have to open all the boxes one by one. You will first check the first box. If it does not contain the coin, you must close it, check the second box, and so on until you find the coin — the way of solving all sub-problems one by one to reach the best possible solution is called Backtracking.
Famous N-Queen puzzle:
The classic textbook example of using Backtracking is the eight-queens puzzle, which asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are k queens arrangements in the board’s first k rows, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned.
For example, the following is a solution for the 4 Queen problem.
Backtracking Algorithm: The idea is to place queens in different columns, starting from the leftmost column. When we put a queen in a queue, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, we backtrack and return false.
Backtracking Algorithm usage:
We can use backtrack-based algorithms in numerous places, including
- Solving puzzles like Sudoku, maze, crosswords, verbal arithmetic, eight queens puzzle, etc.
- Combinatorial optimization problems like knapsack problems, Graph coloring problems, Hamiltonian cycle, etc.
Maybe walking through the algorithm for another problem will clarify what back-tracing means. Let us start with Sudoko. Here, we try filling digits one by one. Whenever the current number cannot lead to a solution, we remove it (backtrack) and try the following number. Repeat this whole until we arrive at a solution.
Better than brute-force?
Is it not a brute-force method? Are we not trying all combinations? How is it better than the brute-force approach?
I want to answer this with an example. Consider the sudoku case. The discussed solution is better than the brute-force approach, which generates all possible combinations of digits and chooses the right one from that list. With the backtracking approach, we drop a set of permutations whenever it backtracks. Practically we will see benefits in terms of runtime and resource usage. But theoretically, the complexity of the algorithm remains n!
When to use Backtracking?
- We must choose the best option from the list of all possible options based on given constraints.
- The ask is to generate permutations and combinations.
