Constraint Satisfaction Problems & The AC-3 Arc Consistency Algorithm

Standard search treats states as atomic black boxes. In contrast, Constraint Satisfaction Problems (CSPs) employ a factored representation consisting of three components:

1. Variables X = {X_1, X_2, ..., X_n}.

2. Domains D = {D_1, D_2, ..., D_n}, where each D_i is a set of allowable values for X_i.

3. Constraints C = {C_1, C_2, ..., C_m}, where each constraint specifies a subset of variables and allowable tuples of values (e.g., X_1 \neq X_2).

A state is an assignment of values to variables. An assignment is consistent if it violates no constraints, and complete if every variable is assigned. A solution is a complete, consistent assignment.

Constraint propagation prunes variable domains before and during search. The most influential propagation algorithm is AC-3 (Arc Consistency 3).

Definition of Arc Consistency:

A directed arc X_i \to X_j is arc-consistent if for every value x \in D_i, there exists at least one value y \in D_j such that (x, y) satisfies the binary constraint between X_i and X_j.

The AC-3 Algorithm Execution:

1. Initialize a queue Q containing all directed binary constraint arcs in the CSP: Q = {(X_i, X_j), (X_j, X_i) \mid for all constrained pairs X_i, X_j}.

2. While Q is not empty:

• Remove an arc (X_i, X_j) from Q.

• Execute Revise(Xi, Xj): For each x \in D_i, if no value y \in D_j satisfies the constraint, remove x from D_i.

• If Revise modified D_i:

- If D_i becomes empty, return FAILURE (no solution exists).

- Otherwise, re-insert into Q all arcs (X_k, X_i) where X_k is a neighbor of X_i (k \neq j).

Time Complexity: An arc (X_k, X_i) can be inserted into Q at most d times (since D_i has at most d values to delete). With c binary constraints, total arc revisions is at most 2c \cdot d. Each revision inspects at most d^2 value pairs. Hence, total AC-3 time complexity is O(c \cdot d^3).

When constraint propagation leaves multiple values in domains, CSP search uses Depth-First Backtracking augmented with three classic heuristics:

1. Minimum Remaining Values (MRV / Most Constrained Variable):

• Selects the unassigned variable with the fewest legal values left in its domain.

• Philosophy: 'Fail-first' — if a variable is going to fail, fail immediately to prune the search tree early.

2. Degree Heuristic (Tie-Breaker for MRV):

• Selects the variable involved in the largest number of constraints with other unassigned variables.

• Philosophy: Reduces the branching factor of future variables by constraining them early.

3. Least Constraining Value (LCV):

• Once a variable is chosen, selects the value that rules out the fewest choices for neighboring unassigned variables.

• Philosophy: 'Fail-last' — leaves maximum flexibility for remaining unassigned variables to find a solution.