Backtracking Search with Propagation

Solving a CSP means assigning a value to every variable so that all constraints are satisfied. Backtracking search does this by assigning variables one at a time and recursing, undoing the assignment when a constraint is violated. Plain backtracking is slow because it discovers conflicts only after committing to an assignment that propagation could have ruled out in advance.

Backtracking search with propagation interleaves the two. After every assignment we enforce arc consistency on the remaining domains. If propagation empties any domain, the current branch is a dead end and we backtrack immediately. The classic variant that re-establishes AC after each branch is called MAC (Maintaining Arc Consistency).

The algorithm is:

1. Enforce arc consistency on the current domains.
2. If some domain is empty, return failure.
3. If every variable's domain is a singleton, return the assignment.
4. Choose an unfixed variable $X$.
5. For each value $v \in \mathrm{dom}(X)$:
   • Save the current domains.
   • Set $\mathrm{dom}(X) \leftarrow \{v\}$ and recurse.
   • If the recursion returns a solution, return it.
   • Otherwise restore the saved domains and try the next $v$.
6. If every value has failed, return failure.

Tiny illustration. Variables $X, Y \in \{1, 2, 3\}$ with $X < Y$. Initial AC reduces the domains to $X \in \{1,2\}$ and $Y \in \{2,3\}$. Branch $X=1$; propagation leaves $Y \in \{2,3\}$. Branch $Y=2$; both domains are singletons. Solution $(X,Y)=(1,2)$.