###
CS4341 Introduction to Artificial Intelligence

Sample Constraint Satisfaction Problems - D 2001

#### Problem 1. Seating Arrangements.

Consider again the problem of seating 6 people at a round table in such
a way that the following constraints are satisfied:
- (C1) Spouses (if any) sit next to each other.
- (C2) People who hate each other don't sit next to each other.

**Part 1.** Construct a constraint net to represent this problem,
assuming that spouses don't hate each other.

**Part 2.** Construct a constraint net to represent this problem,
assuming that spouses may hate each other but nevertheless
they have to sit next to each other. This means that, when in
conflict, constraint C1 takes precedence over constraint C2.

**Part 3.** Extend the constraint net of Part 2 to accommodate the
following additional assumption:

If persons A and B hate each other then

- (1) A's spouse and B hate each other
- (2) B's spouse and A hate each other
- (3) A's spouse and B's spouse hate each other

**Hint:** You may want to write demon procedures using IF-THEN rules.
Remember that those demons should appear only in the connections
between frames.

#### Problem 2. Medicine Interaction.

It is Spring and the flu season is attacking New England!
Suppose that a medical doctor needs your help constructing
a constraint net to find prescriptions for his/her flu patients.
The following table shows the symptoms exhibited by flu patients
and the list of medications that can be prescribed for each symptom.
Symptom Medications
Headache H1, H2, H3
Runny nose R1, R2
Fever F1, F2
Sore throat S1, S2

Assume also that the FDA has found that each the following sets of
medications presents dangerous drug interactions and so drugs in each
set should not be prescribed together.
- (1) {H1,S1}
- (2) {H2,R2,F2,S2}
- (3) {R1,F2,S3}

A patient may be allergic to some drugs. Hence, an appropriate
prescription for a flu patient should consist of 4 non-interacting
medications, one for each symptom, to which the patient is not allergic.
**Part 1.** Construct a constraint net that helps the medical doctor
in finding appropriate prescriptions for his/her flu patients.

**Part 2.** Using label propagation, find an appropriate prescription for
Lucy, who is allergic to F1.

#### Problem 3. The "farmer, fox, goose, and grain" puzzle.

Consider the "farmer, fox, goose, and grain" puzzle (see p. 16
of your textbook). Using a constraint net, represent the constraints
imposed on the location of the farmer and his three possessions.

#### Problem 4. Multimedia Presentation. OPTIONAL

Suppose that you are planning to give a short slide presentation.
The presentation is divided into four parts P_1, P_2, P_3, and P_4,
which you will present sequentially in that order.
For each part P_i you'll show two slides: first S_i1 and then S_i2.
Simultaneously with the two slides, you will play an audio tape A_i.
Using propagation of time interval relations (chapter 12) describe
a constraint need that represents the temporal structure of your
presentation.