Backtracking is a strategy for finding solutions to constraint satisfaction problems.
Constraint satisfaction problems or CSPs are mathematical problems where one must find states or objects that satisfy a number of constraints or criteria. Examples of constraint satisfaction problems; Eight queens puzzle, Map coloring problem, Sudoku (see below), Boolean satisfiability.
Essentially, the idea is to try each possibility until you get the right one. It is a depth-first search
of the set of solutions. During the search, if you try an alternative that doesn't work, you backtrack to the choice
point, the place which presented you with different alternatives, and you try the next alternative. When you have
exhausted the alternatives, you return to the previous choice point and try the next alternative there. If there
are no more choice points, the search fails.
This is usually achieved in a recursive function whereby each instance takes one more variable and alternatively
assigns all the available values to it, keeping the one that is consistent with subsequent recursive calls. Backtracking
is similar to a depth-first search but uses even less space, keeping just one current solution state and updating
it.
In order to speed up the search, when a value is selected, before making the recursive call, the algorithm either
deletes that value from conflicting unassigned domains (forward checking) or checks all the constraints to see
what other values this newly-assigned value excludes (constraint propagation).