Backtracking is a strategy used to find and build a solution incrementally. We start with a possible move and we try to solve the problem with the selected move. If it does not work, we backtrack and then we select another move and so on until we have the problem solved. Due to this behavior, backtracking algorithms will try all possible moves (or a few moves if a solution is found sooner) to solve a problem.
There are some famous problems that can be solved with backtracking:
- The Knight’s tour problem
- N Queen problem
- Rat in a maze
- Sudoku Solver