解斑马拼图(又名斑马拼图)。使用clpfd Prolog库

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.

我已经得到了使用我所选择的约束解算器来解决zebra谜题的练习，并且我使用Prolog clpfd库进行了尝试。

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!

我知道在Prolog中还有其他更常用的方法来解决这个问题，但是这个问题是关于clpfd包的!

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. 英国人住在红房子里
3. The Swedish own a dog
4. 瑞典人养了一只狗。
5. The Danish likes to drink tea
6. 丹麦人喜欢喝茶
7. The green house is left to the white house
8. 绿房子留给了白宫
9. The owner of the green house drinks coffee
10. 绿房子的主人喝咖啡
11. The person that smokes Pall Mall owns a bird
12. 吸烟的人有一只鸟
13. Milk is drunk in the middle house
14. 牛奶在中间的房子里喝
15. The owner of the yellow house smokes Dunhill
16. 黄色房子的主人吸烟
17. The norwegian lives in the first house
18. 挪威人住在第一所房子里
19. The marlboro smoker lives next to the cat owner
20. 吸烟的万宝路香烟就住在猫主人旁边
21. The horse owner lives next to the person who smokes dunhill
22. 马的主人住在登喜路吸烟的人旁边
23. The winfield smoker likes to drink beer
24. 温菲尔德的烟鬼喜欢喝啤酒
25. The norwegian lives next to the blue house
26. 挪威人住在蓝房子旁边
27. The german smokes rothmanns
28. 德国抽烟rothmanns
29. The marlboro smoker has a neighbor who drinks water
30. 这个抽万宝路香烟的人有一个喝水的邻居

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.

房子可以具有的每个属性都被建模为一个变量，例如。“British”、“Dog”、“Green”等属性可以取1到5的值，这取决于它们所处的房子，例如，如果变量“Dog”取值3，那么狗就住在第三个房子里。

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

但是，无论如何，clpfd包不产生解决方案，即使(IMO)问题被正确建模(我使用了与Choco约束求解器完全相同的模型，结果是正确的)。

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.

我是否误解了clpfd中的一个概念，或者我只是漏掉了一些明显的东西?在这里，您可以找到使用Choco和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".

编辑:我认为求解器不能解决问题的原因是它从来没有为变量提供确定的值，而是只提供范围，例如。“鱼1 . . 3 \ / 5”。

2 个解决方案

#1

running your code in SWI-Prolog, I get

在SWI-Prolog中运行代码，我得到

?- 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_different改为all_distinct，我就会得到没有标签的解决方案:

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

正如您所看到的，文档声明all_distinct和all_different的传播更强。运行所建议的示例有助于理解它们之间的区别:

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

#2

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

这里有几个误解:您说“clpfd包不会产生解决方案”，但实际上它会产生一个:

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

我们知道，如果有解，那么鱼要么是1要么是4。让我们尝试1:

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

No. So let's try 4:

不。让我们试着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:

这是一个可行的解决方案。你可以用一种不同的方式得到它比如把Fish包含在要标注的变量中

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

标记的目的是为了检验约束变量的具体值，而不考虑是否有解。巧合的是，在这种情况下，all_distinct/1足够强大，足以产生一个基本的解决方案，但通常情况下，这是不可能的，你最终必须使用标签来获得无条件的(例如)。)答案。当然，一般来说，你还必须标注所有你感兴趣的变量，而不仅仅是它们的一部分。要标记单个变量，可以使用indomain/1，因此将indomain(Fish)附加到上面的第一个查询也可以。我无法重现您在后面的注释中提到的实例化错误，事实上，正如您在上面看到的，最通用的查询解决方案(X, Y)与您所发布的代码一起工作。最后,看看这个:

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