Backtracking is an algorithmic technique that considers searching in every possible combination for solving a computational problem.
There are three types of backtracking problems:
Besides programming, we use backtracking in our everyday lives. Now, it's not exactly retracing steps to find something lost, although we all have been there. We are trying to find a solution using multiple paths or methods to try and solve it. And if one method doesn't work, we go back to where we started so we do not confuse ourself more. If you were to continue on to try to solve the problem while not backtracking, our old methods can distract us or slow us down or denying them could lead us to doing it over and over again.
Backtracking can be used in games like Chess and Sudoku. Here is an activity: Give a coin or an item to a group of friends or under three or more boxes. We check each hand or box and if it does not have the coin, close it and try again. How does this use backtracking? The problem is you are trying to find a solution "the coin", and you are checking each box "method/probable solutions" one by one to see what will get you the desired outcome.
A space state tree is a tree that represents all of the possible states of the problem, from the root as an initial state to the leaf as a terminal state.
In the image shown, S is the starting point to finding the issue, I 1-3 are the intermediate check points, and S 1-3 are solutions. S3 is the end feasible solution.
