Backtracking
Backtracking is an approach to problem solving which is usually applied to constraint satisfaction problems like puzzles. In a backtracking solution, a search path is followed and the algorithm backtracks at a particular point ( also known as decision point ) in the path as soon as it realizes that this path won’t lead to a valid solution and then it follows another path starting from a previous decision point. In this way, different paths are repeatedly explored to arrive at the final solution.
Consider the problem of solving a sudoku. A naive algorithm will try to find every possible arrangement of numbers and checks if the problem can be solved with a particular arrangement but the backtracking algorithm provides a much better and efficient solution.
Backtracking is basically a refinement of the brute-force approach in which the solution to a problem is found using systematic search rather than trying out possible solutions blindly.
Let’s solve some problems using backtracking approach.