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?

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

Solution 2

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

Solution 3

From Wikipedia:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

Backtracking is easily implemented as a recursive algorithm. You look for the solution of a problem of size n by looking for solutions of size n - 1 and so on. If the smaller solution doesn't work you discard it.

That's basically what the code above is doing: it returns true in the base case, otherwise it 'tries' the right path or the left path discarding the solution that doesn't work.

Since the code above it's recursive, it might not be clear where the "backtracking" comes into play, but what the algorithm actually does is building a solution from a partial one, where the smallest possible solution is handled at line 5 in your example. A non recursive version of the algorithm would have to start from the smallest solution and build from there.

Solution 4

I cannot figure out what "backtracking algorithm" means.

An algorithm is "back-tracking" when it tries a solution, and on failure, returns to a simpler solution as the basis for new attempts.

In this implementation,

current_path.remove(p)

goes back along the path when the current path does not succeed so that a caller can try a different variant of the path that led to current_path.

View more solutions

Comments

[Giovanni Botta]

That's a great graphical explanation!

[Elad Benda2]

so you don'r even try F? is this only for algorithms looking for one good result only?

[Elad Benda2]

is this only for algorithms looking for one good result only?

[Willem Van Onsem]

No. Sometimes you are interested in all solutions, or the "best" five (if you can compare two solutions). But from the moment you sometimes need to "destroy" a part of what you have constructed earlier in order to reassign variables, it is called a backtracking algorithm.

[Josef E.]

In this example, essentially. This being recursion/enumeration; one could modify to look for ALL good leaves. But in this situation, we were looking only for one (the first one accessed). @user1065869

[Pete Kirkham]

No, it does not. If you ask prolog, which usually uses backtracking, to solve x=2, y=x then it will not try all values of x or all values of y and return only for the value 2.