Homework

Constraint Satisfaction Problem

In five houses, each with a different colour, live five people of different nationalities, each of whom prefers a different brand of chocolates, a different drink, and a different pet. Given the following facts, answer the questions: “Where does the zebra live, and in which house do they drink water?”

• The Englishman lives in the red house.
• The Spaniard owns the dog.
• The Norwegian lives in the first house on the left.
• The green house is immediately to the right of the ivory house.
• The man who eats Cadburys lives in the house next to the man with the fox.
• Kit Kats are eaten in the yellow house.
• The Norwegian lives next to the blue house.
• The Smarties eater owns snails.
• The Snickers eater drinks orange juice.
• The Ukrainian drinks tea.
• The Japanese eats Milky Ways.
• Kit Kats are eaten in a house next to the house where the horse is kept.
• Coffee is drunk in the green house.
• Milk is drunk in the middle house.

Write down your reason for how you found the solution. What steps did you take? In which order did you try to satisfy each of the constraints?

Email your answers to claude@cse.unsw.edu.au with subject COMP3431 CSP Homework. Deadline Monday 19 September.