CS 4341 D01 - Sample CSP

Computer Science Department

CS4341 Introduction to Artificial Intelligence
Sample Constraint Satisfaction Problems - D 2001

PROF. CAROLINA RUIZ

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.