Arc Consistency (AC-3)

The fundamental operation is the Revise(X, Y) function. For a given arc (X, Y):

• It inspects each value 'a' in the current domain of X.
• It checks if there exists any value 'b' in the domain of Y that satisfies the constraint C(X, Y).
• If no such 'b' exists for a given 'a', then 'a' is removed from the domain of X. The function returns true if the domain of X was actually changed. This boolean return drives the worklist propagation logic.

AC-3 has a worst-case time complexity of O(ed³) and a space complexity of O(e), where:

• e is the number of arcs (directed constraints) in the graph.
• d is the maximum size of any variable's initial domain. The d³ factor arises because Revise can, in the worst case, check all d values in X against all d values in Y (d²), and an arc can be processed up to d times. In practice, with good heuristics and sparse constraints, performance is often far better.

AC-3 is rarely used in isolation. Its primary role is as the inference engine inside Maintaining Arc Consistency (MAC), a complete search algorithm. In MAC, AC-3 (or a more advanced variant like AC-2001) is called at every node of the backtracking search tree after a variable assignment. This aggressively prunes future search space by eliminating values from unassigned variables that are now arc-inconsistent with the current partial assignment.

AC-3 is simpler but less optimal than later algorithms:

• AC-1 & AC-2: Earlier, less efficient versions. AC-1 revisits all arcs after any change.
• AC-4: A more complex, optimal algorithm with O(ed²) worst-case time complexity. It uses counters and support lists to avoid redundant checks but has higher overhead and memory use (O(ed²)).
• AC-2001/3.1: Modern optimal variants that retain AC-3's simplicity by remembering a single latest supporting value for each (variable, value, constraint), achieving O(ed²) complexity. AC-3 remains the practical default due to its simplicity and good average-case performance.

k-Consistency is a generalized hierarchy of local consistency properties. A CSP is k-consistent if, for any set of k-1 variables with a consistent assignment, a consistent value can always be found for any k-th variable.

• 1-Consistency (Node Consistency): Each value satisfies the variable's unary constraints.
• 2-Consistency (Arc Consistency): The property enforced by AC-3.
• 3-Consistency (Path Consistency): Extended to triples of variables. Enforcing higher levels of k-consistency is more powerful but computationally expensive.

A Constraint Optimization Problem (COP) extends a standard CSP by adding an objective function that must be maximized or minimized. The goal is no longer to find any feasible solution, but the best one according to a metric (e.g., minimize cost or maximize efficiency). Solving COPs often involves techniques like branch and bound on top of constraint propagation. AC-3 remains relevant for pruning infeasible regions of the search space during optimization.

Local search algorithms like the min-conflicts heuristic represent a different, incomplete approach to solving CSPs compared to systematic search with AC-3. They start with a complete but potentially invalid assignment and iteratively improve it. At each step, the algorithm selects a conflicted variable and changes its value to the one that results in the minimum number of conflicts with other variables. This method is highly effective for large-scale problems like scheduling and is famously used for the n-queens problem.

The Boolean Satisfiability Problem (SAT) is a canonical NP-complete CSP where variables are Boolean and constraints are clauses. Modern SAT solvers use the Conflict-Driven Clause Learning (CDCL) algorithm, which shares conceptual parallels with CSP techniques. CDCL performs a form of constraint propagation (unit propagation), encounters conflicts, analyzes them to learn new constraints (clauses), and then performs non-chronological backtracking. This is analogous to intelligent backtracking schemes in CSPs like Conflict-Directed Backjumping.