Lecture 07.1: Constraint Satisfaction Problems and Consistency

While traditional search algorithms focus on planning (finding a sequence of actions to reach a goal), Constraint Processing focuses on assignment (identification). In these problems, the path to the goal is irrelevant; the goal itself—a complete, consistent assignment of values—is the only thing that matters.

A Constraint Satisfaction Problem (CSP) is a computational framework defined by three components:

1. $X$: A set of variables $\{X_1, ..., X_n\}$.
2. $D$: A set of domains $\{D_1, ..., D_n\}$, one for each variable.
3. $C$: A set of constraints that specify allowable combinations of values.

A state in a CSP is defined by an assignment of values to some or all variables.

• Consistent Assignment: An assignment that does not violate any constraints.
• Complete Assignment: Every variable is assigned a value.
• Solution: A complete and consistent assignment.

Varieties of Constraints

Constraints limit the values that variables can take:

• Unary constraints: Involve a single variable (e.g., $SA \neq \text{green}$).
• Binary constraints: Involve pairs of variables (e.g., $SA \neq WA$).
• Higher-order constraints: Involve 3 or more variables (e.g., Crypt-arithmetic puzzles).
• Global constraints: Involve an arbitrary number of variables (e.g., Alldiff in Sudoku).
• Preference (soft constraints): Represented by a cost for each assignment, turning the problem into a Constrained Optimization Problem (e.g., Jan prefers teaching in the morning).

Constraint Graphs

A binary CSP can be visualized as a Constraint Graph, where nodes are variables and arcs are constraints.

(In the Map Coloring problem for Australia, adjacent territories cannot share the same color. The graph above shows a valid assignment where connected nodes have different colors. Notice that T (Tasmania) is an independent subproblem!)

Inference and Enforcing Consistency

Before or during the search, we can use Constraint Propagation to eliminate inconsistent values, shrinking the domains of variables and radically reducing the search space.

1. Node Consistency

A variable is node-consistent if every value in its domain satisfies all unary constraints.

• Example: If domain of $A = \{1, 2, 3, 4\}$ and constraint is $A > 2$, we reduce the domain to $D_A = \{3, 4\}$.

2. Arc Consistency

A variable $X$ is arc-consistent with another variable $Y$ (denoted as arc $X \rightarrow Y$) if, for every value $x$ in the domain $D_X$, there exists at least one value $y$ in the domain $D_Y$ that satisfies the binary constraint between $X$ and $Y$. If a value $x$ lacks such "support" in $D_Y$, it is pruned from $D_X$.

[!IMPORTANT] Arc Consistency is Directed: An arc $X \rightarrow Y$ being consistent does not guarantee that the reverse arc $Y \rightarrow X$ is consistent. We must check and enforce consistency in both directions.

Concrete Step-by-Step Example

Consider two variables $X$ and $Y$ with the following domains and a binary inequality constraint:

• Domains: $D_X = \{1, 2, 3\}$, $D_Y = \{2, 3\}$
• Constraint: $X < Y$

Let's evaluate the arc consistency for $X \rightarrow Y$:

1. For $X = 1$: We look for a supporting $y \in D_Y$ such that $1 < y$. Both $y=2$ and $y=3$ work. (Kept)
2. For $X = 2$: We look for a supporting $y \in D_Y$ such that $2 < y$. The value $y=3$ works. (Kept)
3. For $X = 3$: We look for a supporting $y \in D_Y$ such that $3 < y$. No value in $D_Y = \{2, 3\}$ satisfies this. (Removed!)

The revised domain of $X$ becomes $D_X = \{1, 2\}$.

The AC-3 Algorithm

The AC-3 algorithm (Mackworth, 1977) is the standard method for enforcing arc consistency across an entire constraint graph. It maintains a queue of arcs that need to be checked. Whenever a variable's domain is reduced, any constraints pointing into that variable must be re-evaluated, as their supporting values may have disappeared.

Pseudocode

function AC-3(csp) returns false if inconsistency is found, true otherwise
    inputs: csp, a binary CSP with variables X, domains D, constraints C
    local variables: queue, a queue of arcs, initially containing all arcs in csp
    
    while queue is not empty do
        (Xi, Xj) = REMOVE-FIRST(queue)
        if REVISE(csp, Xi, Xj) then
            if size of Di == 0 then 
                return false // Domain Wipe Out (DWO) - no solution exists
            for each Xk in Xi.NEIGHBORS - {Xj} do
                add (Xk, Xi) to queue
    return true

function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
    revised = false
    for each x in Di do
        if no value y in Dj satisfies the constraint between Xi and Xj then
            delete x from Di
            revised = true
    return revised

Walkthrough: The Divisibility Constraint Problem (Rina Dechter's Example)

To see AC-3 in action, let's trace a network of three variables $\{x, y, z\}$ with two divisibility constraints:

• Constraints: $z$ divides $x$ and $z$ divides $y$ (i.e., $x/z$ and $y/z$ are integers).
• Initial Domains:
  • $D_x = \{2, 5\}$
  • $D_y = \{2, 4\}$
  • $D_z = \{2, 5\}$

Let's initialize the queue of directed arcs: $\text{Queue} = \{(x, z), (z, x), (y, z), (z, y)\}$

1. Process $(z, y)$: We check if every $z \in D_z$ has a multiplier in $D_y$ (such that $z$ divides $y$).
   • $z = 2$: Supported by $y = 2$ and $y = 4$ ($2 \mid 2$ and $2 \mid 4$). (Kept)
   • $z = 5$: $5$ does not divide $2$ or $4$. No support! We delete $5$ from $D_z$.
   • Domain update: $D_z = \{2\}$.
   • Propagation: Since $D_z$ changed, we add neighbors of $z$ (except $y$) pointing to $z$ back to the queue. The arc $(x, z)$ is already in the queue, so no new additions are needed.
2. Process $(x, z)$: We check if every $x \in D_x$ has a divisor in $D_z = \{2\}$.
   • $x = 2$: Supported by $z = 2$ ($2 \mid 2$). (Kept)
   • $x = 5$: $z = 2$ does not divide $5$. No support! We delete $5$ from $D_x$.
   • Domain update: $D_x = \{2\}$.
   • Propagation: Since $D_x$ changed, we must add $(z, x)$ to the queue (already there).
3. Process $(z, x)$: Check if every $z \in D_z = \{2\}$ divides some $x \in D_x = \{2\}$. Yes, $2$ divides $2$. (No change).
4. Process $(y, z)$: Check if every $y \in D_y = \{2, 4\}$ has a divisor in $D_z = \{2\}$.
   • $y = 2$: Supported by $z = 2$.
   • $y = 4$: Supported by $z = 2$. (No change).

The queue is now empty. The algorithm terminates successfully, returning: $D_x = \{2\}, \quad D_y = \{2, 4\}, \quad D_z = \{2\}$ This network is now completely arc-consistent!

The Arc Consistency Family: From AC-1 to AC-4

The evolution of arc consistency algorithms reflects a classic computer science trade-off between simplicity, time complexity, and memory overhead.

(Where $n$ is the number of variables, $d$ is the maximum domain size, and $e$ is the number of binary constraint arcs.)