3.2. Filtering

CSP Filtering

Filtering improves CSP performance by pruning variable domains early, reducing the number of branches that violate constraints during backtracking search. Instead of waiting to discover a contradiction deep in the search tree, filtering anticipates conflicts and eliminates them ahead of time. There are multiple approaches to this:

• Forward checking immediately prunes values that violate binary constraints from a variable $X$‘s unassigned neighbors. It does so by checking if $X$‘s domain still has at least one valid value. If a neighbor’s domain becomes empty, a backtrack is triggered.
  ⠀
• Arc consistency (AC-3) is a generalized version of forward checking, such that every value of a variable should be “supported” by at least one compatible value in each of its neighbors. In other words, given an arc $X_i\to X_j$:

1. Begin by storing all arcs $X_i\to X_j\forall i,j$ in a queue $Q$.
2. While $|Q|>0$ or $|\mathrm{dom}(X_i)|>0\forall i$:

• Pop an arc $X_i\to X_j$.
• Enforce the condition that for every value $v\in \mathrm{dom}{X}_i$, there exists some $w\in \mathrm{dom}{X}_j$ such that $(X_i=v,X_j=w)$ satisfies all constraints.
  • If no such $w$ exists, remove $v$ from $X_i$’s domain.
• If at least one value is removed for $X_i$ when enforcing arc consistency for an arc $X_i\to X_j$, add arcs of the form $X_k\to X_i$ to $Q$ for all unassigned variables $X_k$. Do not add duplicate arcs.

3. Perform a backtracking search if $\exists i\mathrm{dom}{X}_i=\varnothing$.
   ⠀

• $k$-Consistency is a generalized version of AC-3