The following logic puzzle is known as Zebra Puzzle or Einstein Puzzle (source: Wikipedia). It was first published in the Life International magazine in 1962. Also, exercise 6.6 in the book is a slight variation of that puzzle.

In five houses, each with a different color, live five persons of different nationality, each of whom prefers a different brand of cigarettes, a different drink, and a different pet. The five houses are arranged in a row (no house has more than 2 neighbors).

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

1. Model the problem as a CSP, that is define variables, their domains and constraints between them. There are different ways of modelling this. Typically you want to have fewer variables and fewer or simpler constraints.
2. Download the material below, implement your model (implement all things marked with TODO).
3. Run the program and compare the results. What does that tell you about the usefulness of different propagation algorithms and heuristics for this problem?

• java project for the lab

The project contains a Main class which sets up and solves the CSP, as well as some additional classes implementing the constraints. You need to implement a few parts in Main.java and a method in DifferByOneConstraint.java (if you need that constraint). To run the code simply run the Main class or use “ant run” on the terminal.

As with all the labs, you can work in groups of up to 4 students.

Hand in a zip file containing:

• the answers to the questions above (in a text/pdf/word file)
• your source code (ideally just the whole project directory)

To create the zip file you can just edit the “student” property in the build.xml and call the “zip” target using ant (execute “ant zip” in the directory containing the build.xml).