Backtracking

Backtracking is a searching algorithm that is a specialised version of DFS used in CSP solvers on search trees. The key intuition is that:

• We search through the space of partial assignments, rather than paths.
• We decide on a suitable value for one variable at a time. The order in which we assign the variables doesn’t matter.
• If a constraint is violated (falsified) during the process of partial assignment, we immediately reject the partial assignment.

This process is done recursively.

• If all variables are set, we print the solution and terminate.
• Otherwise:
  • Pick an unassigned variable $V$ and assign it a value.
  • Test whether the constraints corresponding with $V$ and all other variables of them are assigned.
  • if a constraint is unsatisfied, return (backtrack).
  • Otherwise, we go one level deeper by invoking a recursive call.

Since this is a variant of DFS, it is rather uninformed in how it handles things. The time complexity of backtracking is exponential, given by $\mathcal{O}(d^n)$, where $n$ is the number of variables, and $d$ is the main domain size.

In CSPs, there might be variables that have no possible value, but BT doesn’t detect this until it tries to assign them a value, i.e., an entire sub-tree may be invalidated but we may not know until we try to assign it a variable. This is because basic BT has no sense of forward constraints further in the tree. This motivates the idea of constraint propagation.