Solution of the Zebra puzzle (the so-called Einstein puzzle) using the clopfd Prolog library

Question

I was instructed to solve the zebra riddle with the constraint resolver of my choice, and I tried this using the Prolog clpfd library .

I know that there are other idiomatic ways to solve this problem in Prolog, but this question definitely relates to the clpfd package!

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

There are five houses

• The Englishman lives in a red house.
• Swedish own dog
• Danish loves to drink tea
• The green house remains in the white house.
• Green house owner drinks coffee
• The person who smokes the Pall Mall owns a bird.
• Milk is drunk in the middle house
• Yellow House Owner Smokes Dunhill
• The Norwegian lives in the first house.
• Smoker marlboro lives next to a cat owner
• The owner of the horse lives next to the person who smokes dunhill.
• Winfield smoker loves to drink beer
• A Norwegian lives next to a blue house.
• German smokes rothmanns
• A marlboro smoker has a neighbor who drinks water.

I tried to solve it using the following approach:

Each attribute that a house can have is modeled as a variable, for example. British, Dog, Green, etc. Attributes can take values ​​from 1 to 5, depending on the house in which they are found, for example. if the variable "Dog" takes the value 3, the dog lives in the third house.

This approach simplifies the modeling of neighboring constraints as follows:

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

But somehow, the clpfd package clpfd not provide a solution, although the (IMO) problem is correctly modeled (I used the 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 not understand the concept inside clpfd , or did I just miss something obvious here? In case this helps, here you can find the same approach implemented using Choco and Scala.

---

Edit:. The reason I think the solver cannot solve the problem is because he never comes up with specific values ​​for variables, but only with ranges, for example. "Fish 1..3 / 5".

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 a solution without a 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 can see, the documents show stronger distribution for all_distinct vs all_different . Running the proposed sample will help to understand the difference between the two:

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

Answer 2

There are a few misconceptions here: you state that “the clpfd package does not provide a solution”, but in fact it gives 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 has a value of 1 or 4. Try 1:

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

Not. So try 4:

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

This works and is the main solution to the problem. You can get it in another way, for example, by including Fish in variables that should be labeled:

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

The purpose of labeling is to accurately try specific values ​​for restricted variables, regardless of whether a solution really exists. Coincidentally, all_distinct / 1 is strong enough to give a basic solution in this case, but on the whole this is certainly not the case, and you should ultimately use the marking to get an unconditional (that is, no more pending restrictions) answer. Of course, in the general case, you should also designate all the variables that interest you, and not just part of them, as you did at the beginning. To tag a single variable, you can use indomain / 1, so adding indomain (Fish) to the first request above will also work. I could not reproduce the error of creating the instance described in the additional comment, in fact, as you see above, the most general request (X, Y) works with the code that you published. Finally check this out:

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