Backtracking and Depth First Search

In very simple terms, we can think of backtracking as building and exploring a search tree in a depth first manner. The root node of the tree, or the "path" to the leaf node, represents a candidate solution that can be evaluated. So as we traverse through each path, we're testing a solution. So in the diagram below, A -> B -> D is one possible solution.

If the candidate path qualifies as a working solution, then it is kept as an alternative. Otherwise, the search continues in a depth first manner. In other words, once a solution is found, the algorithm backtracks (goes back a step, and explores another path from the previous point) to explore other tree branches to find more solutions.

Efficiency Gains

For constraint satisfaction problems, the search tree is "pruned" by abandoning branches of the tree that would not lead to a potential solution. Thus, we're constantly cutting down the search time and making it more efficient than an exhaustive or complete search. Let's now jump straight into how all of this is done via examples you might see on interview day.