What is Backtracking Programming??
Recursion is the key in backtracking programming. As the name suggests we backtrack to find the solution. We start with one possible move out of many available moves and try to solve the problem if we are able to solve the problem with the selected move then we will print the solution else we will backtrack and select some other move and try to solve it. If none if the moves work out we will claim that there is no solution for the problem.
Generalized Algorithm:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Pick a starting point. | |
| while(Problem is not solved) | |
| For each path from the starting point. | |
| check if selected path is safe, if yes select it | |
| and make recursive call to rest of the problem | |
| If recursive calls returns true, | |
| then return true. | |
| else | |
| undo the current move and return false. | |
| End For | |
| If none of the move works out, return false, NO SOLUTON. |
Problems on Backtracking
- Backtracking — N Queens Problem
- Backtracking — N Queens Problem — Better Solution
- Backtracking — Knight’s Tour Problem
- The Word Break Problem
- Backtracking — Rat In A Maze Puzzle
- Backtracking — Search a Word In a Matrix