Constraint Satisfaction Problem
- by Carl Smotricz
I'm struggling my way through Artificial Intelligence: A Modern Approach in order to alleviate my natural stupidity. In trying to solve some of the exercises, I've come up against the "Who Owns the Zebra" problem, Exercise 5.13 in Chapter 5. This has been a topic here on SO but the responses mostly addressed the question "how would you solve this if you had a free choice of problem solving software available?"
I accept that Prolog is a very appropriate programming language for this kind of problem, and there are some fine packages available, e.g. in Python as shown by the top-ranked answer and also standalone. Alas, none of this is helping me "tough it out" in a way as outlined by the book.
The book appears to suggest building a set of dual or perhaps global constraints, and then implementing some of the algorithms mentioned to find a solution. I'm having a lot of trouble coming up with a set of constraints suitable for modelling the problem. I'm studying this on my own so I don't have access to a professor or TA to get me over the hump - this is where I'm asking for your help.
I see little similarity to the examples in the chapter.
I was eager to build dual constraints and started out by creating (the logical equivalent of) 25 variables: nationality1, nationality2, nationality3, ... nationality5, pet1, pet2, pet3, ... pet5, drink1 ... drink5 and so on, where the number was indicative of the house's position.
This is fine for building the unary constraints, e.g.
The Norwegian lives in the first house:
nationality1 = { :norway }.
But most of the constraints are a combination of two such variables through a common house number, e.g.
The Swede has a dog:
nationality[n] = { :sweden } AND pet[n] = { :dog }
where n can range from 1 to 5, obviously. Or stated another way:
nationality1 = { :sweden } AND pet1 = { :dog }
XOR nationality2 = { :sweden } AND pet2 = { :dog }
XOR nationality3 = { :sweden } AND pet3 = { :dog }
XOR nationality4 = { :sweden } AND pet4 = { :dog }
XOR nationality5 = { :sweden } AND pet5 = { :dog }
...which has a decidedly different feel to it than the "list of tuples" advocated by the book:
( X1, X2, X3 = { val1, val2, val3 }, { val4, val5, val6 }, ... )
I'm not looking for a solution per se; I'm looking for a start on how to model this problem in a way that's compatible with the book's approach. Any help appreciated.
