4

我正在尝试在 Prolog中解决爱因斯坦谜语。

我编写的程序遇到了困难，基本方法是添加所有约束并让 Prolog 找出唯一可能的解决方案。

问题是 Prolog 找到 0 个解决方案。我已经隔离了使程序从给定解决方案变为无解决方案的约束，但我不明白为什么。

/*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。

我想帮助理解为什么会这样。我注意到在部分解决方案中，挪威语出现了两次，这可能表明存在问题。

4

1 回答 1

6

Here is a general way how you can solve this problem for yourself. Actually, you really started in a quite promising direction: You tried to remove goals. But then, who was at fault in your case? The line you commented out or the rest? You cannot say that for sure, since the resulting program already worked. But there is a very similar and much more promising way: Try to generalize your program as much as possible such that it still fails. In this manner, you will obtain a smaller program that is responsible for the failure. That is, within the remaining visible part has to be an error!

Here is what I got by removing goals (adding a * in front) and by replacing some terms by _.

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

This fragment still fails, thus the error has to be in the visible part of the program.

It seems to be essential that all the house colors are present. There is only one goal that does not contain any house color at all... see it?

于 2017-08-22T19:48:34.210 回答