Arc Consistency (AC-3)

AC-3 enforces arc consistency, a specific type of local consistency. For every binary constraint between two variables (X, Y), the algorithm ensures that for every value 'a' remaining in the domain of X, there exists at least one value 'b' in the domain of Y such that the pair (a, b) satisfies the constraint. This property is checked locally for each arc (directed constraint) but propagates globally as domains are reduced.

The algorithm's core is a worklist (queue) of arcs to be revised. It begins with all arcs in the constraint graph. When the domain of a variable Y is reduced during a revision, all arcs pointing to Y (except the one just processed) are added back to the worklist. This ensures that changes propagate efficiently without redundant checks, making AC-3 sound (never removes a solution value) and complete for arc consistency (achieves the strongest possible domain reduction under this property).

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.

Constraint propagation is the overarching inference technique that uses the logical relationships defined by constraints to reduce the search space. It works by iteratively eliminating values from variable domains that cannot participate in any solution. AC-3 is a specific, efficient algorithm for enforcing one type of propagation: arc consistency. Other forms include node consistency (unary constraints) and path consistency (triples of variables).

Maintaining Arc Consistency (MAC) is a complete search algorithm that powerfully combines backtracking search with full arc consistency enforcement. At each node in the search tree (after each variable assignment), MAC runs an algorithm like AC-3 to prune the domains of future variables. This aggressive pruning often makes MAC significantly more efficient than vanilla backtracking, though it incurs higher computational cost per node. It's a standard algorithm for solving difficult CSPs.

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.