Prolog/解决逻辑谜题

让我们用一个有趣的逻辑问题来练习。你可以在脑海中或在草稿纸上想出解决方案，然后我们使用 Prolog 来解决它。

考虑一群十个朋友想要去世界某个地方的新城市旅行。他们对七个潜在目的地进行了投票

开罗
伦敦
北京
莫斯科
孟买
内罗毕
雅加达

一个城市获得了四票，两个城市分别获得了两票，两个城市分别获得一票，剩余两个城市没有获得任何票。每个城市获得了多少票？

北京和开罗的票数不同。
莫斯科要么获得最多票数，要么获得零票。
开罗的票数比雅加达多。
在上面的城市列表中，每个获得两票的城市在列表中都紧邻着一个未获得任何票的城市。
要么雅加达的票数比伦敦少一票，要么雅加达的票数比北京少一票。

Prolog 中的解决方案

这是 Prolog 中的一种可能的解决方案。我们将使用城市名称来表示每个城市获得的票数。使用 Prolog 鼓励的生成-测试范式，我们将生成所有投票排列并根据谜题规则对其进行测试。

投票分配

一个城市获得了四票，两个城市分别获得了两票，两个城市分别获得一票，剩余两个城市没有获得任何票。我们可以使用内置的排列谓词。

permutation([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta],[4,2,2,1,1,0,0])

规则 1

北京和开罗的票数不同。我们可以使用内置的比较运算符。回想一下，分号表示 OR。

(Cairo < Beijing; Cairo > Beijing)

规则 2

莫斯科要么获得最多票数，要么获得零票。

(Moscow = 4; Moscow = 0)

规则 3

开罗的票数比雅加达多。这是一个直接的比较操作。

(Cairo > Jakarta)

规则 4

在上面的城市列表中，每个获得两票的城市在列表中都紧邻着一个未获得任何票的城市。此规则更难解决。你可以考虑修改内置的 member 谓词以查找对。在这里，我们定义了一个 count 谓词来计算对在列表中出现的次数。然后，我们查找列表中 0,2 出现两次的列表。这是针对 [X,Y]，X \= Y 的特殊情况模式匹配器。对于 [X,X] 的一般情况将不起作用，因为它在匹配后会跳过匹配的 2 个元素。

 count([],_,0).
 count([X,Y|Rest],[X,Y],N) :- count(Rest,[X,Y],N1), N is N1 + 1.
 count([Z|Rest],[X,Y],N) :- Z \= X, count(Rest, [X,Y], N).

 count([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta], [0,2], 2)

规则 5

要么雅加达的票数比伦敦少一票，要么雅加达的票数比北京少一票。回想一下，'is' 会评估操作。

(Jakarta is (London-1); Jakarta is (Beijing-1))

完整解决方案

count([],_,0).
count([X,Y|Rest],[X,Y],N) :- count(Rest,[X,Y],N1), N is N1 + 1.
count([Z|Rest],[X,Y],N) :- Z \= X, count(Rest, [X,Y], N).

votesFor([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta]) :-
    permutation([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta],[4,2,2,1,1,0,0]),
    (Cairo < Beijing; Cairo > Beijing),
    (Moscow = 4; Moscow = 0),
    (Cairo > Jakarta),
    count([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta], [0,2], 2),
    (Jakarta is (London-1); Jakarta is (Beijing-1)).

Prolog 返回以下值

?- votesFor([Cairo, London, Beijing, Moscow, Mumbai, Nairobi, Jakarta]).
Cairo = 4,
London = Moscow, Moscow = 0,
Beijing = Mumbai, Mumbai = 2,
Nairobi = Jakarta, Jakarta = 1 .

事实上，Prolog 返回了上述解决方案八次。这是因为两个城市在三个不同的位置共享了相同的票数总数（2^3 = 8），而 Prolog 找到了每个到达相同解决方案的不同方法。