Back to practice exercises.

1: Background Reading

• 4.1 Features and States
• 4.2 Possible Worlds, Variables, and Constraints
• 4.3 Generate-and-Test Algorithms
• 4.4 Solving CSPs Using Search
• 4.5 Consistency Algorithms
• 4.6 Domain Splitting

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.