Backtracking is a problem solving technique for the problems based on yes/no decision based problems. Here you are making a decision and if you encounter a result that is not acceptable because of a wrong decision you made, you will go back to the step where you made wrong decision and try to make different decision.
Usually backtracking solution is accompanied with recursion. Because of this, sometime make us difficult to understand the solution. In the end o the chapter we shall look at a coding example that will make it easy.
The best example to understand backtracking is “ball in a maze” problem.
Problem statement is as below:
A ball will be placed at the starting of the maze; your job is to move the ball such that it will reach at the end of the maze.
Below is the diagram
From the above image, we can see that the ball can move left, right, down. By using these 3 operations you need to make the ball reach the end.
Here you will be making series of decision to make the ball reach the end. At some point you might reach to a dead end, then you backtrack to the point where you can make a different decision. Hence this is called as backtracking.
Let us solve the problem theoretically:
The ball will start at tile 1 and has to reach to tile 9 by making series of “yes” “no” based decision.
Let’s first follow the path
1 -> 2 -> 3
Then it will go down to “6” and continue the path
1 -> 2 -> 3 -> 6 -> 5 -> 4
as 4 is the end, it will go to 7
1 -> 2 -> 3 -> 6 -> 5 -> 4 -> 7
Now at “7” it cannot go anywhere. Hence you need to backtrack to 4, then to 5.
1 -> 2 -> 3 -> 6 -> 5 -> 8 -> 9
As you can see, we made number of decision on how to traverse. Backtracking is based on brute force approach. You continue till you reach a point where the result is not that you have expected. Then you traverse back to a point where you have an accepted result and then take other decision.