在Prolog中解决爱因斯坦难题

Question

我正在尝试用Prolog解决爱因斯坦难题。

我遇到了困难，我的基本方法是添加所有约束条件，然后让Prolog找出唯一可能的解决方案。

问题是Prolog找不到任何解决方案。我已经分离出导致程序从给定的解决方案到无解的约束条件，但我不明白为什么会这样。

/*There are five houses*/
exists(A, list(A,_,_,_,_)).
exists(A, list(_,A,_,_,_)).
exists(A, list(_,_,A,_,_)).
exists(A, list(_,_,_,A,_)).
exists(A, list(_,_,_,_,A)).

middle_house(A, list(_,_,A,_,_)).

first_house(A, list(A,_,_,_,_)).

nextTo(A, B, list(B,A,_,_,_)).
nextTo(A, B, list(_,B,A,_,_)).
nextTo(A, B, list(_,_,B,A,_)).
nextTo(A, B, list(_,_,_,B,A)).
nextTo(A, B, list(A,B,_,_,_)).
nextTo(A, B, list(_,A,B,_,_)).
nextTo(A, B, list(_,_,A,B,_)).
nextTo(A, B, list(_,_,_,A,B)).

/* each statement will be described using the clues 
house conatins: Color,Owner, Drinks, Smokes, Pet*/
riddle(Houses):-
    /*exists(house(red, englishman, _,_,_),Houses),*/
    nextTo(house(_,norwegian,_,_,_), house(blue,_,_,_,_), Houses),
    exists(house(_,spanish,_,_, dog), Houses),
    exists(house(green, _, coffee, _,_), Houses),
    exists(house(_, ukrain, tea,_,_), Houses),
    nextTo(house(white,_,_,_,_), house(green,_,_,_,_), Houses),
    exists(house(_,_,_,marlbero, cat),Houses),
    exists(house(yellow,_,_,time,_), Houses),
    middle_house(house(_,_,milk,_,_), Houses),
    first_house(house(_,norwegian,_,_,_), Houses),
    nextTo(house(_,_,_,_,fox), house(_,_,_,montena,_), Houses),
    nextTo(house(_,_,_,time,_), house(_,_,_,_,horse), Houses),
        exists(house(_,_,orange,lucky,_), Houses),
    exists(house(_,japanese,parlament,_), Houses).

目前的解决方案是这样的：

?- riddle(Houses).
Houses = list( house(green, norwegian, coffee, marlbero, cat),
               house(white, spanish, orange, lucky, dog),
               house(yellow, norwegian, milk, time, fox),
               house(blue, ukrain, tea, montena, horse),
               house(_G7257, japanese, parlament, _G7260)).

如果我取消第一行的注释，那么相同的语句会返回false。

我希望能够理解为什么会这样。 我注意到在部分解决方案中，挪威人出现了两次，这可能是问题所在。

- Belgi

---

同时，“nextTo(house(white,,,,), house(green,,,,), Houses)”并不够严格。根据原始谜题，绿色的房子在白色房子的右侧，而不仅仅是“旁边”。 - lurker

您的 riddle/1 谓词中的最后一行缺少一个 house 参数：exists(house(_,japanese,parlament,_), Houses)。应该是 exists(house(_,japanese,_,parlament,_), Houses)。 - lurker

Answer 1

这里有一个通用的方法，可以帮助你解决这个问题。实际上，你已经开始了一个非常有前途的方向：试图删除目标。但是，在你的情况下，是哪一行出了问题呢？你不能确定，因为最终的程序已经正常工作了。但是有一种非常相似且更加有前途的方法：尽可能地泛化你的程序，使其仍然失败。通过这种方式，你将获得一个负责失败的更小的程序。也就是说，在剩余的可见部分必须有一个错误！

以下是我通过删除目标（在前面添加*）并替换一些术语为_所得到的结果：

:- initialization(riddle(_Sol)).
:- op(950, fy, *).
*_.
riddle(Houses):-
    exists(house(red, _/* englishman */, _,_,_),Houses),
    nextTo(house(_,_/* norwegian */,_,_,_), house(blue,_,_,_,_), Houses),
    * exists(house(_,spanish,_,_, dog), Houses),
    * exists(house(green, _, coffee, _,_), Houses),
    * exists(house(_, ukrain, tea,_,_), Houses),
    nextTo(house(white,_,_,_,_), house(green,_,_,_,_), Houses),
    * exists(house(_,_,_,marlbero, cat),Houses),
    exists(house(yellow,_,_,_/* time */,_), Houses),
    * middle_house(house(_,_,milk,_,_), Houses),
    * first_house(house(_,norwegian,_,_,_), Houses),
    * nextTo(house(_,_,_,_,fox), house(_,_,_,montena,_), Houses),
    * nextTo(house(_,_,_,time,_), house(_,_,_,_,horse), Houses),
    * exists(house(_,_,orange,lucky,_), Houses),
    exists(house(_,_/* japanese */,_/* parlament */,_), Houses).

这个片段仍然失败，因此错误必须在程序的可见部分中。似乎所有房子的颜色都是必要的。只有一个目标不包含任何房子的颜色...看到了吗？

- false