Backtracking
-
Backtracking is a problem solving method that recursively iterates through all the possible options to find the correct output. The name backtracking is because, once a solution is identified or if one path is identified as not the correct solution, the algorithm traverses back to the previous nodes to find different possible solutions. This traversal continues till all the possible solutions are identified.
Let us consider an example:
The following image shows a graph with start and end positions. We are required to find all the shortest paths between the start and end. Beginning from the first node all possible paths are traversed to find the final output.
Backtracking can be used for any of the following use cases.
- Decision - Check if a solution exists. Can exit after finding the first of the many possible answers.
- Optimization - Best possible solution. Complete traversal needed.
- Enumeration - All possible solutions. Complete traversal needed.
-
Backtracking Algorithm
Backtracking is a kind of brute-force search and can be achieved using recursive function calls or using iterators like for or while loops. Time complexity of backtracking algorithms is usually very high and is always above Linear Time Complexity line.
A basic back tracking algorithm can be explained as below.
- Start.
- Input the data structure D.
- Loop the data structure.
- Check if D(i) is a solution.
- If true, add D(i) to list of solutions.
- If false, check next node.
- Display output.
- Stop.
-
Backtracking Applications
Backtracking is an important part of DSA. Many algorithms like Tree Search, Depth First Search utilizes Backtracking technique to find the solutions.
This process can be used to solve many types of puzzles. Can be used for finding the solution of games like Sudoku, Crossword etc. Backtracking also forms the basis of logic based programming languages like Icon and Planner.
