Solving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library

Question

I have been given an exercise to solve the zebra puzzle using a constraint solver of my choice, and I tried it using the Prolog clpfd library.

I am aware that there are other more idiomatic ways to solve this problem in Prolog, but this question is specifically about the clpfd package!

So the specific variation of the puzzle (given that there are many of them) I'm trying to solve is this one:

There are five houses

1. The Englishman lives in the red house
2. The Swedish own a dog
3. The Danish likes to drink tea
4. The green house is left to the white house
5. The owner of the green house drinks coffee
6. The person that smokes Pall Mall owns a bird
7. Milk is drunk in the middle house
8. The owner of the yellow house smokes Dunhill
9. The norwegian lives in the first house
10. The marlboro smoker lives next to the cat owner
11. The horse owner lives next to the person who smokes dunhill
12. The winfield smoker likes to drink beer
13. The norwegian lives next to the blue house
14. The german smokes rothmanns
15. The marlboro smoker has a neighbor who drinks water

I tried to solve it with the following approach:

Each attribute a house can have is modeled as a variable, e.g. "British", "Dog", "Green", etc. The attributes can take values from 1 to 5, depending on the house in which they occur, e.g. if the variable "Dog" takes the value 3, the dog lives in the third house.

This approach makes it easy to model neighbor constraints like this:

def neighbor(X, Y) :-
    (X #= Y-1) #\/ (X #= Y+1).

But somehow, the clpfd package does not yield a solution, even though (IMO) the problem is modeled correctly (I used the exact same model with the Choco constraint solver and the result was correct).

Here is the complete code:

:- use_module(library(clpfd)).

neighbor(X, Y) :-
    (X #= (Y - 1)) #\/ (X #= (Y + 1)).

solve([British, Swedish, Danish, Norwegian, German], Fish) :-

    Nationalities = [British, Swedish, Danish, Norwegian, German],
    Colors = [Red, Green, Blue, White, Yellow],
    Beverages = [Tea, Coffee, Milk, Beer, Water],
    Cigarettes = [PallMall, Marlboro, Dunhill, Winfield, Rothmanns],
    Pets = [Dog, Bird, Cat, Horse, Fish],

    all_different(Nationalities),
    all_different(Colors),
    all_different(Beverages),
    all_different(Cigarettes),
    all_different(Pets),

    Nationalities ins 1..5,
    Colors ins 1..5,
    Beverages ins 1..5,
    Cigarettes ins 1..5,
    Pets ins 1..5,

    British #= Red, % Hint 1
    Swedish #= Dog, % Hint 2
    Danish #= Tea, % Hint 3

    Green #= White - 1 , % Hint 4
    Green #= Coffee, % Hint 5,
    PallMall #= Bird, % Hint 6

    Milk #= 3, % Hint 7
    Yellow #= Dunhill, % Hint 8,
    Norwegian #= 1, % Hint 9

    neighbor(Marlboro, Cat), % Hint 10
    neighbor(Horse, Dunhill), % Hint 11
    Winfield #= Beer, % Hint 12

    neighbor(Norwegian, Blue), % Hint 13
    German #= Rothmanns, % Hint 14,
    neighbor(Marlboro, Water). % Hint 15

Did I misunderstand a concept within clpfd, or am I simply missing something obvious here? In case it helps, here you can find the same approach implemented using Choco and Scala.

---

Edit: The reason why I believe that the solver isn't able to solve the problem ist that it never comes up with definite values for the variables, but only with ranges, e.g. "Fish 1..3\/5".

Headliner

Use label(Vars) or labeling(Options, Vars) tro solve the problem. – Edmee

"label" only works if there is a definite result, whereas what I am getting for every variable are only ranges (as explained in the edit). – Headliner

If your CLP(FD) would have "Expr in Set", then one could formalize neighbor(X,Y) :- X - Y in [-1,1]. – Berky

You can define neighbour/2 as: abs(X-Y) #= 1. – Lannylanolin

@CookieMonster: You can write V in -1\/1 but permitting expressions for the first argument would make it defaulty. – Ammerman

Answer 1

running your code in SWI-Prolog, I get

?- solve(X),label(X).
X = [3, 5, 2, 1, 4].

Without label:

?- solve(X).
X = [3, _G3351, _G3354, 1, _G3360],
_G3351 in 4..5,
all_different([_G3351, _G3386, _G3389, 2, _G3395]),
all_different([3, _G3351, _G3354, 1, _G3360]),
_G3386 in 3..5,
all_different([_G3386, _G3444, 1, _G3450, _G3360]),
_G3389 in 1\/3..5,
_G3389+1#=_G3478,
_G3492+1#=_G3389,
_G3395 in 1\/3..5,
_G3478 in 2..6,
_G3444#=_G3478#<==>_G3529,
_G3444 in 2..5,
_G3444#=_G3556#<==>_G3553,
_G3444#=_G3568#<==>_G3565,
_G3444#=_G3492#<==>_G3577,
_G3450 in 2\/5,
all_different([_G3354, 4, 3, _G3450, _G3614]),
_G3360 in 2\/4..5,
_G3354 in 2\/5,
_G3614 in 1..2\/5,
_G3614+1#=_G3556,
_G3568+1#=_G3614,
_G3556 in 2..3\/6,
_G3553 in 0..1,
_G3565#\/_G3553#<==>1,
_G3565 in 0..1,
_G3568 in 0..1\/4,
_G3492 in 0..4,
_G3577 in 0..1,
_G3577#\/_G3529#<==>1,
_G3529 in 0..1.

If I change all_different to all_distinct I get the solution without label:

....
all_distinct(Nationalities),
all_distinct(Colors),
all_distinct(Beverages),
all_distinct(Cigarettes),
all_distinct(Pets),
....

?- solve(X).
X = [3, 5, 2, 1, 4].

As you see, the docs state stronger propagation for all_distinct vs all_different. Running the proposed sample help to understand the difference between those:

?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]), all_distinct(Vs).
false.

?- maplist(in, Vs, [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]), all_different(Vs).
Vs = [_G419, _G422, _G425, _G428, _G431, _G434],
_G419 in 1\/3..4,
all_different([_G419, _G422, _G425, _G428, _G431, _G434]),
_G422 in 1..2\/4,
_G425 in 1..2\/4,
_G428 in 1..3,
_G431 in 1..3,
_G434 in 1..6.

Bellini

all_distinct did the trick. Thanks. I was always trying to do something like solve(X,Y) (see the updated solve signature) and I got ERROR: Arguments are not sufficiently instantiated, but that doesn't occur when using all_distinct. – Headliner

At first glance I noted Fish was a singleton in original code, but fiddling the code I didn't get the consequences, that you have rightly found. – Bellini

all_distinct is extremely slower than all_different followed by label in all the cases I tested. – Manrope

@fpg1503: I never benchmarked them. If you have some publishable example, could be interesting to chart the 'strength' enhancement vs augmented complexity for both algorithms – Bellini

Answer 2

There are several misconceptions here: You state "the clpfd package does not yield a solution", but actually it does yield one:

?- solve(Ls, Fish), label(Ls).
Ls = [3, 5, 2, 1, 4],
Fish in 1\/4,
all_different([5, 3, _G3699, 2, Fish]),
_G3699 in 1\/4,
_G3699+1#=_G3727,
_G3741+1#=_G3699,
_G3727 in 2\/4..5,
2#=_G3727#<==>_G3766,
_G3766 in 0..1,
_G3792#\/_G3766#<==>1,
_G3792 in 0..1,
2#=_G3741#<==>_G3792,
_G3741 in 0\/2..3.

So we know that if there is a solution, then Fish is either 1 or 4. Let's try 1:

?- solve(Ls, Fish), label(Ls), Fish = 1.
false.

No. So let's try 4:

?- solve(Ls, Fish), label(Ls), Fish = 4.
Ls = [3, 5, 2, 1, 4],
Fish = 4.

This works and is a ground solution to the problem. You can get it in a different way for example by including Fish in the variables that are to be labeled:

?- solve(Ls, Fish), label([Fish|Ls]).
Ls = [3, 5, 2, 1, 4],
Fish = 4 ;
false.

The purpose of labeling is exactly to try concrete values for constrained variables, independent of whether there actually is a solution. By coincidence, all_distinct/1 is strong enough to yield a ground solution by itself in this case, but in general this is of course not the case and you must eventually use labeling to obtain an unconditional (i.e., no more pending constraints) answer. Of course you must then in general also label all variables that are of interest to you, not just a subset of them as you did initially. To label a single variable, you can use indomain/1, so appending indomain(Fish) to the first query above would also work. I could not reproduce the instantiation error you mentioned in a further comment, in fact as you see above the most general query solve(X, Y) works with the code you posted. Finally, check this out:

neighbor(X, Y) :- abs(X-Y) #= 1.

Lannylanolin