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 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
....