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

Answer 1

There are several libraries for CSP solving:

• Gecode (C++)
• Choco (Java)
• clp(*) module in SICStus Prolog

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

On the other hand if you want to implement your general constraint solver, an idea to implement a CSP Solver: build a constraint graph, where the nodes are the constraint variables and constraints the connections. For every variable store the possible domain, and build a notification mechanism. The constraints are notified when its related variables change, and then start a propagation process: by looking at the current values of the related variables reduce the domains of possible variables.

Propagation example:

• Variables (with domain): X - {1,2,3,4,5} - Y {1,2,3,4,5}
• Constraint: X + Y < 4
• When the constraint propagates, you can infer, that neither X nor Y can be 3, 4 nor 5, because then the constraint would fail, so the new domains are: X- {1,2} Y - {1,2}
• Now both domains of X and Y have changed the constraints listening to X and Y should be notified to propagate.

It is possible that propagation is not enough. In this case a backtracking/backjumping search is used: we try to select the value of a single variable, propagate the changes, etc.

This algorithm is considered quite fast while it is easy to understand. I have some implementation that solves our special case of problems very efficiently.