在序言中解决爱因斯坦之谜 [英] Solving Einstein Riddle in Prolog

问题描述

我正在尝试解决Prolog中的爱因斯坦之谜.

I am trying to solve Einstein Riddle in Prolog.

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

I am having a difficulty with the program I wrote, the basic method was to add all constraints and let Prolog figure out the only possible solutions.

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

The problem is that Prolog finds 0 solutions. I have isolated the constraint that makes the program go from a given solution to no solutions, but I don't understand why.

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

当前的解决方案是这样:

The current solution to this is this:

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

and if I uncomment the first line then that same statement returns false.

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

I would like help understanding why this is the case. I noted that in the partial solution the Norwegian appears twice and that this might indicate the problem.

推荐答案

以下是您自己解决此问题的一般方法.实际上，您实际上是从一个非常有希望的方向开始的:您试图删除目标.但是，在您的案件中谁在过错呢?您注释掉的那一行还是其他?您不能肯定地说出来，因为生成的程序已经可以工作了.但是，有一种非常相似且更有希望的方法:尝试尽可能泛化程序，以使程序仍然失败.这样，您将获得一个较小的程序，该程序负责该故障.也就是说，在其余可见部分内会出现错误！

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?

这篇关于在序言中解决爱因斯坦之谜的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！