Constraint Satisfaction Problem

Question

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.

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 modeling 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 a 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.

Answer 1

There are several libraries for CSP solving:

• Gecode (C++)

• Choco (Java)

And there are many more. But these can be used for efficient constraint solving.

You can refer to the link for better understanding:

http://aima.cs.berkeley.edu/newchap05.pdf

If you wish to know more about Artificial Intelligence then visit this Artificial Intelligence Course.