Practice Exercise 4.A
Arc Consistency

## 2: Learning Goals

• Build a constraint network for a set of constraints.
• Verify whether a network is arc consistent.
• Define/read/write/trace/debug the arc consistency algorithm. Compute its complexity and assess its possible outcomes.
• Define/read/write/trace/debug domain splitting and its integration with arc consistency.

## 3: Directed Questions

1. What does it mean for an arc to be consistent? [solution]

2. How can we enforce consistency of an arc <X,r(X,Y)>? [solution]

3. What does it mean for a network to be arc consistent? [solution]

4. What are the possible outcomes of the arc consistency algorithm? [solution]

## 4: Exercise: Arc Consistency

1. Consider the case where the arc consistency algorithm terminates and some domains have multiple values. Is there guaranteed to be a solution? [solution] To think about this issue, consider the CSP problem with three binary variables A, B, and C; with the three constraints A != B, B != C and A != C. Draw the corresponding constraint network, trace arc consistency and look at the outcome.

## 5: Learning Goals Revisited

• Build a constraint network for a set of constraints.
• Verify whether a network is arc consistent.
• Define/read/write/trace/debug the arc consistency algorithm. Compute its complexity and assess its possible outcomes.
• Define/read/write/trace/debug domain splitting and its integration with arc consistency.