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
In this book, we will learn the Rat in a Maze and Sudoku Solver problems as they are easier to understand. However, you can find the source code for other backtracking problems ...
