使用clpfd Prolog库解决斑马拼图（又名爱因斯坦拼图） [英] Solving the Zebra puzzle (aka. Einstein puzzle) using the clpfd Prolog library
问题描述
我已经练习使用我选择的约束求解器来解决斑马拼图，我尝试使用 Prolog clpfd库。
我知道还有其他更常用的方法来解决这个问题在Prolog，但这个问题特别关于 clpfd 包！
我想解决的是这一个：
有五个房子
- 英国人住在红楼
- 瑞典人拥有一只狗
- 丹麦人喜欢喝茶
- 这座温室被留在白宫。
- 温室的主人喝咖啡 b $ b
- 抽取Pall Mall的人拥有一只鸟
- 中间喝牛奶
- winfield吸烟者喜欢喝啤酒
- 挪威人住在蓝色房子旁边
- 德国人吸烟rothmanns
- marlboro吸烟者有一个饮水的邻居
我试图用以下方法解决它：
房子的每个属性都被建模为变量，例如British，
Dog，Green等。属性可以取从1到5的值，这取决于它们发生的房子
。如果变量Dog取值3，那狗就住在
第三宫。
这种方法可以方便地建模邻近约束，如下所示：
def neighbor（X，Y）： -
（X＃= Y-1）＃\ /（X＃= Y + 1）。
但是不管怎么说， 以下是完整的代码： 我误解了 clpfd 产生一个解决方案，即使（IMO）问题被正确建模（我使用与
： - use_module（library（clpfd））。
邻居（X，Y）： -
（X＃=（Y-1））＃\ /（X＃=（Y + 1））。
solve（[英国，瑞典语，丹麦语，挪威语，德语]，鱼）： -
民族= [英国，瑞典语，丹麦语，挪威语，德语] $ b Colors = [Red，Green，Blue，White，Yellow]，
饮料= [茶，咖啡，牛奶，啤酒，水]，
香烟= [PallMall，Marlboro，Dunhill，Winfield，Rothmanns ]，
宠物= [狗，鸟，猫，马，鱼]，
all_different（国籍），
all_different（颜色），
all_different ，
all_different（Cigarettes），
all_different（Pets），
国籍ins 1..5，
颜色ins 1..5，
饮料ins 1..5，
Cigarettes ins 1..5，
宠物入口1..5，
英国＃=红色，％Hint 1
瑞典语＃ =狗，％提示2
丹麦语＃=茶，％提示3
绿色＃=白色 - 1，％提示4
绿色＃=咖啡，％提示5，
PallMall＃= Bird，％Hint 6
牛奶＃= 3，％Hint 7
黄色＃= Dunhill，％Hint 8，
挪威语＃= 1，提示9
邻居（Marlboro，Cat），％Hint 10
邻居（Horse，Dunhill），％Hint 11
Winfield＃=啤酒，％Hint 12
邻居（挪威语，蓝色），％Hint 13
德语＃= Rothmanns，％Hint 14，
邻居（Marlboro，Water）。 ％Hint 15
clpfd ，或者我只是缺少一些明显的在这里？如果有帮助，此处您可以找到相同的
在SWI-Prolog中运行代码， >
？ - solve（X），label（X）。
X = [3，5，2，1，4]。
没有标签：
？ - 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在1 \ / 3..5，
_G3389 + 1＃= _ G3478，
_G3492 + 1＃= _ G3389，
_G3395在1 \ / 3..5，
_G3478在2..6中，
_G3444＃= _G3478＃> _G3529，
_G3444在2..5中，
_G3444＃= _G3556＃ => _G3553，
_G3444＃= _G3568＃> _G3565，
_G3444＃= _G3492＃== _G3577，
_G3450 in 2\ / 5 ，
all_different（[_ G3354，4，3，_G3450，_G3614]），
_G3360在2 \ / 4..5，
_G3354在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。
如果我将 all_different 更改为 all_distinct 我得到没有标签的解决方案：
....
all_distinct（国籍），
all_distinct ，
all_distinct（Beverages），
all_distinct（Cigarettes），
all_distinct（Pets），
....
？ 。
X = [3，5，2，1，4]。
正如你所看到的，文档对 all_distinct vs all_different 。运行建议的示例有助于理解这些示例之间的区别：
？ - maplist（in，Vs，[1 \ / 3 .4,1.2.2 / 4,1.2 / 1. / 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在1..2 \ / 4，
_G425在1..2 \ / 4，
_G428在1..3，
_G431在1..3中，
_G434在1..6中。
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
- The Englishman lives in the red house
- The Swedish own a dog
- The Danish likes to drink tea
- The green house is left to the white house
- The owner of the green house drinks coffee
- The person that smokes Pall Mall owns a bird
- Milk is drunk in the middle house
- The owner of the yellow house smokes Dunhill
- The norwegian lives in the first house
- The marlboro smoker lives next to the cat owner
- The horse owner lives next to the person who smokes dunhill
- The winfield smoker likes to drink beer
- The norwegian lives next to the blue house
- The german smokes rothmanns
- 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".
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.
这篇关于使用clpfd Prolog库解决斑马拼图（又名爱因斯坦拼图）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
