Solving CSPs:

In a combined 3rd and 5th grade class, students can be 8, 9, 10, and 11 years old. We are trying to solve for the ages of Ann, Bob, Claire, and Doug (abbreviations: A, B, C, D). Consider the following constraints:

No students is older in years than Clair (but may be the same age)

Bob is two years older than Ann

Bob is younger in years than Doug. Complete the following questions:

1. (5 pts) Draw the constraint graph.

2. (3 pts) Suppose we are using the AC-3 algorithm for arc consistency. How many total arcs will be en-queued when the algorithm begins execution?

3. (9 pts) Assuming all ages {8, 9, 10, 11} are possible for each student before running arc consistency, manually run arc consistency on only arc from A to B.

(a) What values on A remain viable after this operation?

(b) What values on B remain viable after this operation?

(c) Assuming there are no arcs left in the list of arcs to be processed, which arc(s) would be added to the queue for processing after this operation?

4. (8 pts) Suppose we enforce arc consistency on all arcs. What ages remain in each persons domain?

Q1. Solving CSPs (25 points) In a combined 3rd and 5th grade class, students can be 8, 9, 10, and 11 years old. We are trying to solve for the ages of Ann, Bob, Claire, and Doug (abbreviations: A, B, C, D). Consider the following constraints: No students is older in years than Clair (but may be the same age) Bob is two years older than Ann Bob is younger in years than Doug. Complete the following questions: 1. (5 pts) Draw the constraint graph. 2. (3 pts) Suppose we are using the AC-3 algorithm for arc consistency. How many total arcs will be en-queued when the algorithm begins execution? 3. (9 pts) Assuming all ages {8, 9, 10, 11} are possible for each student before running arc con- sistency, manually run arc consistency on only arc from A to B. (a) What values on A remain viable after this operation? (b) What values on B remain viable after this operation? (c) Assuming there are no arcs left in the list of arcs to be processed, which arc(s) would be added to the queue for processing after this operation? 4. (8 pts) Suppose we enforce arc consistency on all arcs. What ages remain in each person's domain