序言中的 Zebra 解决方案如何工作？

Question

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：同时发布问题的文本（有点著名）以供参考：

一排五个彩色房子，每个房子都有主人、宠物、香烟和饮料。
英国人住红房子
西班牙人有条狗。
他们在温室里喝咖啡。
乌克兰人喝茶。
绿房子紧挨着白房子。
温斯顿吸烟者有一条蛇。
在黄色的房子里，他们抽 Kool。
中屋喝牛奶
挪威人住在左起第一栋房子里。
切斯特菲尔德吸烟者住在养狐狸的人附近。
在有马的房子附近的房子里，他们抽 Kool。
好彩烟民喝果汁
日本人抽肯特
挪威人住在蓝房子附近

谁拥有斑马谁喝水？

Answer 1

房子列表 Hs 从来没有 是空的。它是在一开始就创建的

length(Hs, 5)

所以它是一个包含五个最初未初始化的逻辑变量的列表，当它们被依次调用时，它们会被所有后续目标实例化，特别是被你提到的相同 member/2 目标实例化。

要查看此示例，请尝试：

32 ?- L=[A,B,C], member(1, L).
L = [1, B, C] ;
L = [A, 1, C] ;    % three solutions are found by Prolog
L = [A, B, 1].     % in turn, one after another

那些无法完成的调用（无法实例化剩余的自由逻辑变量）会导致特定搜索分支失败。

一个例子：

33 ?- L=[1,2,C], member(3,L).    % a check succeeds, while 
L = [1, 2, 3], C = 3.            % instantiating the `C` logvar

34 ?- L=[1,2,3], member(3,L).    % a check succeeds
L = [1, 2, 3].

35 ?- L=[1,2,3], member(4,L).    % a check fails
false.

最后只剩下成功的实例化，从而形成解决方案，当Hs中的所有逻辑变量都完全实例化时，地面。

Answer 2

How come the Houses(Hs) predicate not fail the various member(elem, list) checks, if the list is actually empty all the time?

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

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

了解 Prolog 的一件重要事情是目标或查询不仅仅意味着“这个陈述是真的吗？”。 Prolog 目标或查询意味着“在什么情况下 这个陈述是正确的？”。 Prolog 将尽力向您描述您的查询变为真的情况。

因此，即使我们之前对 Hs 一无所知，在执行此 length 查询时，GNU Prolog 会说：

| ?- length(Hs, 5).

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

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

也许您被以下事实误导了：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 目标的进一步计算可以进一步实例化列表。这就是构建 Zebra 谜题解决方案的原因：Prolog 构建了一个实际描述解决方案的数据结构，而不是仅仅对“这个谜题有解决方案”的问题回答“是”。

序言中的 Zebra 解决方案如何工作？

How does this Zebra solution in prolog work?

prolog

zebra-puzzle