时间戳

首页 > 解决方案 > prolog 中的 Zebra 解决方案如何工作？

prolog - prolog 中的 Zebra 解决方案如何工作？

问题描述

zebra_owner(Owner) :-
    houses(Hs),
    member(h(Owner,zebra,_,_,_), Hs).

water_drinker(Drinker) :-
    houses(Hs),
    member(h(Drinker,_,_,water,_), Hs).


houses(Hs) :-
    length(Hs, 5),                                            %  1
    member(h(english,_,_,_,red), Hs),                         %  2
    member(h(spanish,dog,_,_,_), Hs),                         %  3
    member(h(_,_,_,coffee,green), Hs),                        %  4
    member(h(ukrainian,_,_,tea,_), Hs),                       %  5
    adjacent(h(_,_,_,_,green), h(_,_,_,_,white), Hs),         %  6
    member(h(_,snake,winston,_,_), Hs),                       %  7
    member(h(_,_,kool,_,yellow), Hs),                         %  8
    Hs = [_,_,h(_,_,_,milk,_),_,_],                           %  9
    Hs = [h(norwegian,_,_,_,_)|_],                            % 10
    adjacent(h(_,fox,_,_,_), h(_,_,chesterfield,_,_), Hs),        % 11
    adjacent(h(_,_,kool,_,_), h(_,horse,_,_,_), Hs),              % 12
    member(h(_,_,lucky,juice,_), Hs),                         % 13
    member(h(japanese,_,kent,_,_), Hs),                       % 14
    adjacent(h(norwegian,_,_,_,_), h(_,_,_,_,blue), Hs),          % 15
    member(h(_,_,_,water,_), Hs),       % one of them drinks water
    member(h(_,zebra,_,_,_), Hs).       % one of them owns a zebra

adjacent(A, B, Ls) :- append(_, [A,B|_], Ls).
adjacent(A, B, Ls) :- append(_, [B,A|_], Ls).

如果列表实际上一直是空的，为什么houses(Hs)谓词不会通过各种检查？member(elem, list)我知道这听起来可能是个愚蠢的问题，但围绕 Prolog 进行思考实际上很难，尤其是在多年的面向对象编程之后。任何帮助表示赞赏！

编辑：我没有提到我问序言的查询，就是这个zebra_owner(Owner)

编辑2：还发布问题的文本（有点著名）以供参考：

  1. 一排五座彩色的房子，每座都有一个主人、一只宠物、香烟和一杯饮料。
  2. 英国人住在红房子里。
  3. 西班牙人有一条狗。
  4. 他们在温室里喝咖啡。
  5. 乌克兰人喝茶。
  6. 绿房子紧挨着白房子。
  7. 温斯顿吸烟者有一条蛇。
  8. 在黄色的房子里，他们抽 Kool。
  9. 在中间房子里，他们喝牛奶。
  10. 挪威人住在左边第一个房子里。
  11. 切斯特菲尔德吸烟者住在养狐狸的人附近。
  12. 在有马的房子附近的房子里，他们抽着库尔。
  13. Lucky Strike 吸烟者喝果汁。
  14. 日本人抽肯特。
  15. 挪威人住在蓝屋附近。

谁拥有斑马，谁喝水？

标签： prologzebra-puzzle

解决方案

如果列表实际上一直是空的，Houses(Hs) 谓词为什么不会通过各种成员（elem，list）检查？

那是因为列表实际上不是空的！Prolog 中的空列表是[]. 它不包含任何元素。

但是调用中的列表houses(Hs)由该谓词中的第一个目标控制，即length(Hs, 5). 这个目标是什么意思？

了解 Prolog 的重要一点是，目标或查询不仅仅意味着“这个陈述是真的吗？”。Prolog 目标或查询意味着“在什么情况下这个陈述是真实的？”。Prolog 将尝试向您描述使您的查询为真的情况。

因此，即使我们之前完全不知道Hs，在执行这个length查询时，GNU Prolog 会说：

| ?- length(Hs, 5).

Hs = [_,_,_,_,_]

如果是 形式，那么length(Hs, 5)就变为真。这不是一个空列表。它甚至不是一个可能为空的列表。这是一个绝对包含五个元素的列表。我们对这些元素一无所知！但是列表的长度绝对是固定的。 Hs[_, _, _, _, _]

也许你被 Prolog 允许你谈论一个肯定有元素但其元素还不知道的列表的事实误导了。这是典型的面向对象语言中不可能实现的概念。但我们不知道元素的事实并不意味着那里什么都没有，即列表是空的。

至于member调用如何成功：同样，它们不仅仅是检查“是”X的成员Hs。它们是问题，意思是“在什么情况下是X成员Hs？”。同样，Prolog 会为您做一些工作来描述这些情况：

| ?- length(Hs, 5), member(x, Hs).

Hs = [x,_,_,_,_] ? ;

Hs = [_,x,_,_,_] ? ;

Hs = [_,_,x,_,_] ? ;

Hs = [_,_,_,x,_] ? ;

Hs = [_,_,_,_,x]

x的成员也是如此，Hs如果x是 的第一个元素Hs，或者第二个，或者第三个，等等。在每种情况下，“描述情况”意味着 Prolog 实际上将列表的适当元素（之前是一个变量）绑定到元素x。对于这些可能性中的每一个，member目标之后的进一步计算可以进一步实例化列表。这就是建立斑马谜题解决方案的原因：Prolog 建立了一个实际描述解决方案的数据结构，而不只是对“这个难题有解决方案”这个问题回答“是”。

推荐阅读