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 找到了每個到達相同解決方案的不同方法。