Back to practice exercises.
1: Background Reading
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
 What does it mean for an arc to be consistent? [solution]
 How can we enforce consistency of an arc <X,r(X,Y)>? [solution]
 What does it mean for a network to be arc consistent? [solution]
 What are the possible outcomes of the arc consistency algorithm? [solution]
4: Exercise: Arc Consistency
 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.
