使用 Prolog 解决一个“Layton Puzzle”

Solving a "Layton Puzzle" with Prolog

我为本月的 Logic for Programmers 版本准备了很多内容。 其中包括，我正在完全重写关于逻辑编程语言的章节。

最初，我用谜题求解器来展示这种范式，比如 eight queens 或者 four-coloring。 许多其他的演示也是如此！ 人类解决这些问题需要创造力和洞察力，所以程序能做到这一点感觉很神奇。 但我正在尝试写一本关于实用技术的书，我希望我所谈论的一切都是 有用 的。 所以在 v0.9 中，我将用一些新的程序来替换这些例子，这些程序可能会让人们认为 Prolog 可以在他们的日常工作中帮助他们。

另一方面，对于一份新闻通讯来说，展示一个谜题求解器是很酷的。 最近我偶然发现了我的朋友 Pablo Meier 的 这篇文章，他在文章中使用 Prolog 解决了一个电子游戏谜题：Footnote 1 × Close dialog See description below 给纯文本阅读者的摘要：我们有一个包含 10 个 true/false 问题（表示为 a/b）的测试，以及四个学生的尝试。 给定前三个学生的分数，我们必须算出第四个学生的分数。

bbababbabb = 7
baaababaaa = 5
baaabbbaba = 3
bbaaabbaaa = ???

你可以在 这里 看到 Pablo 的解决方案，并在 SWI-prolog 这里 尝试一下。 非常酷！ 但是在花了太长时间学习 Prolog 仅仅是为了写这该死的书的章节之后，我想看看我是否能比他更优雅地完成它。 代码和谜题剧透如下。

（通常在这里我会链接到我写的一个更温和的介绍，但我想这是我第一次在网上写关于 Prolog 的东西？嗯，这里有一个 Picat intro 代替）

程序

你可以在 SWISH 在线尝试所有这些，或者直接跳转到我的最终版本 这里。

:- use_module(library(dif)).  % Sound inequality
:- use_module(library(clpfd)). % Finite domain constraints

首先是一些导入。 dif 允许我们写 dif(A, B)，如果 A 和 B 不 相等，则为真。 clpfd 允许我们写 A #= B + 1 来表示 “A 比 B 大 1”。Footnote 2

我们会说学生提交的答案和答案 key 都是列表，其中每个值都是 a 或 b。 在 Prolog 中，小写标识符是 原子（就像其他语言中的符号），而以大写字母开头的标识符是 变量。 Prolog 找到匹配方程式的变量值（合一）。 模式匹配非常非常棒。

% ?- 表示查询
?- L = [a,B,c], [Y|X] = [1,2|L], B + 1 #= 7.
B = 6,
L = [a, 6, c],
X = [2, a, 6, c],
Y = 1

接下来，我们递归地定义 score/3Footnote 3。

% 学生的测试分数
% score(student answers, answer key, score)
score([], [], 0).
score([A|As], [A|Ks], N) :-
  N #= M + 1, score(As, Ks, M).
score([A|As], [K|Ks], N) :- 
  dif(A, K), score(As, Ks, N).

第一个 key 是学生的答案，第二个是答案 key，第三个是最终分数。 基本情况是空测试，分数为 0。 否则，我们获取每个列表的头部值并比较它们。 如果它们相同，我们加 1 分，否则我们保持相同的分数。

请注意，我们不能写 if x then y else z，而是使用模式匹配来有效地表达 (x && y) || (!x && z)。 Prolog 确实有一个条件运算符，但它会阻止回溯，所以有什么意义呢？？？

关于双向性的简短休息

Prolog 最酷的事情之一：所有纯粹的逻辑谓词都是双向的。 我们可以使用 score 来检查我们期望的分数是否正确：

?- score([a, b, b], [b, b, b], 2).
true

但我们也可以给它答案和一个 key，并要求它给出分数：

?- score([a, b, b], [b, b, b], X).
X = 2

或者 我们可以给它一个 key 和一个分数，然后问 “哪些测试答案会有这个分数？”

?- score(X, [b, b, b], 2).
X = [b, b, _A],
dif(_A,b)
X = [b, _A, b],
dif(_A,b)
X = [_A, b, b],
dif(_A,b)

不同的值写成 _A，因为我们从未告诉 Prolog 该数组 只能 包含 a 和 b。 我们稍后会修复这个问题。

好的，回到程序

现在我们有了一种计算分数的方法，我们想要找到一个可能的答案 key，它与我们所有的观察结果相匹配，即给每个人正确的分数。

key(Key) :-
  % Figure it out
  score([b, b, a, b, a, b, b, a, b, b], Key, 7),
  score([b, a, a, a, b, a, b, a, a, a], Key, 5),
  score([b, a, a, a, b, b, b, a, b, a], Key, 3).

到目前为止，我们还没有明确说明 Key 的长度与学生答案的长度相匹配。 这由 score 隐式验证（两个列表需要同时为空），但显式添加 length(Key, 10) 作为 key/1 的子句是一个好主意。 我们还应该明确说明 Key 的每个元素要么是 a，要么是 b。Footnote 4 现在我们 可以 编写第二个谓词来说明 Key 具有正确的 “类型”：

keytype([]).
keytype([K|Ks]) :- member(K, [a, b]), keytype(Ks).

但是 “生成匹配约束的列表” 是一件经常出现的事情，我们不想为每个约束编写单独的谓词！ 因此，经过一番挖掘，我找到了一个更优雅的解决方案：maplist。 设 L=[l1, l2]。 那么 maplist(p, L) 等价于子句 p(l1), p(l2)。 它也接受部分谓词：maplist(p(x), L) 等价于 p(x, l1), p(x, l2)。 所以我们可以写Footnote 5

contains(L, X) :- member(X, L).
key(Key) :-
  length(Key, 10),
  maplist(contains([a,b]), L),
  % the score stuff

现在，让我们查询 Key：

?- key(Key)
Key = [a, b, a, b, a, a, b, a, a, b]
Key = [b, b, a, b, a, a, a, a, a, b]
Key = [b, b, a, b, a, a, b, b, a, b]
Key = [b, b, b, b, a, a, b, a, a, b]

所以实际上有四个 不同 的 key 都可以解释我们的数据。 这是否意味着这个谜题坏了并且有多个不同的答案？

不是

这个谜题不是要找出答案 key 是什么，而是要找出第四个学生的分数。 如果我们查询它，我们看到所有四个解决方案都给他的分数相同：

?- key(Key), score([b, b, a, a, a, b, b, a, a, a], Key, X).
X = 6
X = 6
X = 6
X = 6

哈！ 我真的很喜欢谜题看起来好像坏了，但每个 “替代” 解决方案仍然给出相同的谜题答案。

程序总长度：15 行代码，而原始代码为 80 行。 去你的，Pablo。

（顺便说一句，你可以通过编写 findall(X, (key(Key), score($answer-array, Key, X)), L). 一次获得所有答案。）

我仍然不喜欢用谜题来教学

我在 书中 使用的实际示例是 “分析版本控制提交图” 和 “规划一系列基础设施变更”，这些示例比需要解决一个谜题更有可能在工作中出现。 你将在下一个版本中看到它们！