Backtracking Search

Backtracking search is a variation of the Depth First Search in which we do:

• Single-variable assignments Only assignment to one variable at each level of the search tree, this accounts for commutativity: e.g. assigning A to red then B to green is the same as B to green then A to red. This reduces paths from $n{!}^{\ast }{m}^n$ to $m^n$.
• For-each assignment Check for failure. Backtracks on failure to next assignment. If all assignments fail, return failure.