Why is this called backtracking?

Question

I have read in Wikipedia and have also Googled it,

but I cannot figure out what "Backtracking Algorithm" means.

I saw this solution from "Cracking the Code Interviews"

and wonder why is this a backtracking algorithm?

Answer 1

Backtracking is a form of recursion, at times.

This boolean based algorithm is being faced with a choice, then making that choice and then being presented with a new set of choices after that initial choice.

---

Conceptually, you start at the root of a tree; the tree probably has some good leaves and some bad leaves, though it may be that the leaves are all good or all bad. You want to get to a good leaf. At each node, beginning with the root, you choose one of its children to move to, and you keep this up until you get to a leaf.(See image below)

Explanation of Example:

1. Starting at Root, your options are A and B. You choose A.
2. At A, your options are C and D. You choose C.
3. C is bad. Go back to A.
4. At A, you have already tried C, and it failed. Try D.
5. D is bad. Go back to A.
6. At A, you have no options left to try. Go back to Root.
7. At Root, you have already tried A. Try B.
8. At B, your options are E and F. Try E.
9. E is good. Congratulations!

Source: upenn.edu

Answer 2

"Backtracking" is a term that occurs in enumerating algorithms.

You built a "solution" (that is a structure where every variable is assigned a value).

It is however possible that during construction, you realize that the solution is not successful (does not satisfy certain constraints), then you backtrack: you undo certain assignments of values to variables in order to reassign them.

---

Example:

Based on your example you want to construct a path in a 2D grid. So you start generating paths from (0,0). For instance:

(0,0)
(0,0) (1,0) go right
(0,0) (1,0) (1,1) go up
(0,0) (1,0) (1,1) (0,1) go left
(0,0) (1,0) (1,1) (0,1) (0,0) go down
Oops, visiting a cell a second time, this is not a path anymore
Backtrack: remove the last cell from the path
(0,0) (1,0) (1,1) (0,1)
(0,0) (1,0) (1,1) (0,1) (1,1) go right
Oops, visiting a cell a second time, this is not a path anymore
Backtrack: remove the last cell from the path
....