「Prolog中誰是理髮師」邏輯謎題

Question

我正在閱讀Raymond Smullyan的「嘲笑一隻知更鳥」。在這本書中有一個難題，是這樣的：

這個故事的塞維利亞和西班牙的 著名的塞維爾（這其實沒有）之間如有雷同，純屬巧合 。在這個神話般的塞維利亞小鎮，男性居民在那些人身上戴假髮，只在那些他們喜歡的日子裏戴假髮。在所有日子裏，沒有兩個居民行爲相似;也就是說，給定任何兩名男性居民，至少有一天其中一人戴假髮，另一人不戴。 給定任何男性居民X和Y，居民Y被稱爲 是X的追隨者，如果Y在X所有日子都戴假髮。 此外，由於任何居民X，Y和Z，居民Z的說 是X和Y的追隨者，如果Z穿着上的所有日子， X和Y都做假髮。

五位居民被命名爲Alfredo，Bernardo，Ben- ito，Roberto和Ramano。下面的事實是已知的 關於他們：

事實1 ..貝爾納多和貝尼託是相反的在他們的假髮 - ing習慣;也就是說，在任何一天，其中一人戴假髮 ，另一人不戴。

情況2：羅伯特和Ramano同樣對立。事實3：拉馬諾在那些和那些日子戴假髮 當阿爾弗雷多和貝尼託都穿一個。

塞維利亞只能有一個理髮店，和下面的事實 知道關於他：

事實4：貝爾納是阿爾弗雷多和理髮師的追隨者。事實5：鑑於任何男性居民X，如果Bernardo是Alfredo和X的較低級別，則理髮師單獨是X 的追隨者。

阿爾弗雷多·只穿黑色假髮;貝爾納多隻戴白色 假髮;貝尼託只穿着灰色假髮;羅伯託只穿着紅色 假髮;拉瑪諾只穿棕色假髮。

一個復活節早上，理髮師被認爲戴假髮。 他穿什麼顏色？

我想通了，這將是有趣的序言，以解決這個問題，但我卡住了，而早：

isOpposite(bernardo, benito ). 
isOpposite(benito , bernardo). 
isOpposite(roberto , ramano ). 
isOpposite(ramano , roberto ). 

wears(alfredo , black). 
wears(bernardo, white). 
wears(benito , gray ). 
wears(roberto , red ). 
wears(ramano , brown). 

whatWearsTheBarber(WigColor) :- 
    member(Barber, [ alfredo, benito, bernardo, roberto, ramano ]), 
    wears(Barber, WigColor). 

我不知道如何有效編碼有人通過一些其他的人，我根據這些信息不知道如何推理。我遵循了Prolog中其他一些邏輯謎題的解決方案，但是我找不出解決方案。

編輯：下面是Smulyan的書複製的解決方案：

步驟1：首先，證明了羅伯託是 理髮的追隨者。

好，考慮在其上理髮戴假髮的任何一天。 阿爾弗雷多在當天戴假髮或者他不戴。假設Alfredo 。然後貝爾納多當天還戴假髮 ，因爲貝爾納多是阿爾弗雷多和理髮師的追隨者。所以 貝尼託不能在那天戴假髮，因爲他對着貝爾納多的 。然後Ramano不能戴假髮的那一天， 因爲他只穿那些日子假髮當阿爾弗雷多和 貝尼託都做了，貝尼託沒有一個在這一天。由於 Ramano不戴假髮就在這一天，然後羅伯託必須的，因爲 羅伯託相反Ramano。這證明，在 上理髮戴假髮，如果阿爾弗雷多也做， 然後也是如此羅伯託任何一天。

現在，關於哪個理髮師戴假髮 但阿爾弗雷多沒有一天是什麼？那麼，因爲阿爾弗雷多沒有，那麼它實際上並不是阿爾弗雷多和貝尼託都這樣做的;因此 拉馬諾不，由事實3，因此羅伯託不，因此羅伯託，由 事實2.因此，羅伯託在任何一天戴理髮 和阿爾弗雷多不 - 事實上，他在所有的日子戴假髮 不管理髮師，阿爾弗雷多都不會。 這證明了在其上理髮戴着假髮 任何一天，羅伯託也做，無論是否阿爾弗雷多不 或不穿那一天的假髮。所以羅伯託確實是理髮師的追隨者。

Answer 1

EDIT2：由於@ killy9999發佈從書中我決定重寫我的Prolog能夠反映Smullyan的推理解決方案的一部分。原始的部分解決方案保存在下面。

首先一些基本數據結構

person(alfredo). 
person(benito). 
person(roberto). 
person(ramano). 
person(bernardo). 

day([_Alfredo,_Benito,_Bernardo,_Roberto,_Romano]). 

% barber(alfredo). % Follows from Fact 4. 
barber(benito). 
% barber(bernardo). % Follows from Fact 4. 
barber(roberto). 
barber(romano). 

wearsWig(alfredo,[1,_X,_Y,_Z,_W]). 
wearsWig(benito,[_X,1,_Y,_Z,_W]). 
wearsWig(bernardo,[_X,_Y,1,_Z,_W]). 
wearsWig(roberto,[_X,_Y,_Z,1,_W]). 
wearsWig(romano,[_X,_Y,_Z,_W,1]). 

noWig(alfredo,[0,_X,_Y,_Z,_W]). 
noWig(benito,[_X,0,_Y,_Z,_W]). 
noWig(bernardo,[_X,_Y,0,_Z,_W]). 
noWig(roberto,[_X,_Y,_Z,0,_W]). 
noWig(romano,[_X,_Y,_Z,_W,0]). 

那麼我們有兩種類型的一致性條件。一個事實是，對方不會同時戴假髮。另一來自事實3和情況4

consistent2(_D,[]). 
consistent2(D,[(X,Y)|Os]):-wearsWig(X,D),noWig(Y,D),consistent2(D,Os). 
consistent2(D,[(X,Y)|Os]):-noWig(X,D),wearsWig(Y,D),consistent2(D,Os). 

consistent3(O,G):-consistent3(O,_D,G). 

consistent3(_O,_D,[]). 
consistent3(O,D,[(X,Y,Z)|Gs]):- 
    wearsWig(X,D),wearsWig(Y,D),wearsWig(Z,D), 
    consistent2(D,O),consistent3(O,D,Gs). 
consistent3(O,D,[(_X,Y,_Z)|Gs]):- 
    noWig(Y,D),consistent2(D,O),consistent3(O,D,Gs). 
consistent3(O,D,[(_X,_Y,Z)|Gs]):- 
    noWig(Z,D),consistent2(D,O),consistent3(O,D,Gs). 

fact3(D):-wearsWig(romano,D),wearsWig(alfredo,D),wearsWig(benito,D). 
fact3(D):-noWig(alfredo,D),noWig(romano,D). 
fact3(D):-noWig(benito,D),noWig(romano,D). 

這足以證明，羅伯特·遵循理髮（步驟1）：

?- person(Barber),barber(Barber), 
    O = [(benito,bernardo),(roberto,romano)], 
    G = [(bernardo,alfredo,Barber),(romano,alfredo,benito)], 
    consistent3(O,D,G),fact3(D), 
    wearsWig(Barber,D),noWig(roberto,D). 
false. 

因此排除了羅馬諾作爲理髮。

我們也已經得到了（步驟2）貝爾納如下羅伯託和Alfredo：

?- person(Barber)barber(Barber), 
    O = [(benito,bernardo),(roberto,romano)], 
    G = [(bernardo,alfredo,Barber),(romano,alfredo,benito)], 
    consistent3(O,D,G),fact3(D), 
    wearsWig(alfredo,D),wearsWig(roberto,D),noWig(bernardo,D). 
false. 

下一個步驟（步驟3）需要使用事實5，這是一個普遍的說法（也適用於塞維利亞的所有男性居民）很難在Prolog中編碼。

consistent4(_D,_Barber,[]). 
consistent4(D,Barber,[X|Xs]):- 
    wearsWig(X,D1),wearsWig(alfredo,D1), 
    noWig(bernardo,D1),consistent4(D,Barber,Xs). 
consistent4(D,Barber,[X|Xs]):- 
    wearsWig(X,D),wearsWig(alfredo,D), 
    wearsWig(bernardo,D),wearsWig(Barber,D), 
    consistent4(D,Barber,Xs). 

現在定義根謂詞和花哨的顏色：

wears(alfredo, black). 
wears(bernardo, white). 
wears(benito, gray). 
wears(roberto, red). 
wears(ramano, brown). 

whatWearsTheBarber(WigColor):- 
    person(Barber), 
    day(Easter), 
    barber(Barber), 
    wearsWig(Barber,Easter), 
    fact3(Easter), 
    G=[(bernardo,alfredo,Barber),(romano,alfredo,benito)], 
    O=[(benito,bernardo),(roberto,romano)], 
    consistent2(Easter,O), 
    consistent3(O,D,G), 
    X=[alfredo,benito,bernardo,roberto,romano], 
    consistent4(D,Barber,X), 
    wears(Barber, WigColor). 

以下SWI-Prolog的查詢顯示紅色是唯一的答案

?- findall(WigColor,whatWearsTheBarber(WigColor),B),list_to_set(B,R). 
B = [red, red, red, red, red, red, red, red, red|...], 
R = [red]. 

感謝安德魯·庫克。我從他的回答中借鑑。

下面的文本是最初發布和生產的註釋答案。

---

編輯：拼圖實際上是相當困難的，因爲一個有跟蹤多日，不僅是特別的復活節。以下解決方案僅在特定日期考慮塞維利亞的情況才大大減少搜索。

可能更容易考慮爲代表的名單未知的關係在塞維利亞市的情況：

[ [WearsWig,IsBarber], ... , [WearsWig,IsBarber] ] 

本羣體，我們可以規定

seville(S) :- 
     S=[Benito,Bernardo,Roberto,Ramano,Alfredo], 
     opposite(Benito,Bernardo), 
     opposite(Roberto,Ramano), 
     fact3(Ramano,Alfredo,Benito), 
     fact4(Bernardo,Alfredo), 
     noBarber(Bernardo),noBarber(Alfredo), 
     onlyOneBarberWearsWig(S). 

相關謂詞定義如下：

noWig([0,_X]). 
wearsWig([1,_X]). 

isBarber([_X,1]). 
noBarber([_X,0]). 

opposite(X,Y):-noWig(X),wearsWig(Y). 
opposite(X,Y):-noWig(Y),wearsWig(X). 


fact3(X,Y,Z):-wearsWig(X),wearsWig(Y),wearsWig(Z). 
fact3(X,Y,_Z):-noWig(X),noWig(Y). 
fact3(X,_Y,Z):-noWig(X),noWig(Z). 

fact4(X,Y):-wearsWig(X),wearsWig(Y),wearsWig(Z),isBarber(Z). 
fact4(_X,Y):-noWig(Y). 

onlyOneBarberWearsWig([X|Xs]):-isBarber(X),wearsWig(X),noBarbers(Xs). 
onlyOneBarberWearsWig([X|Xs]):-noBarber(X),onlyOneBarberWearsWig(Xs). 
noBarbers([]). 
noBarbers([X|Xs]):-noBarber(X),noBarbers(Xs). 

barbersWigColor([_X,_Y,_Z,_U,Alfredo],black):-isBarber(Alfredo). 
barbersWigColor([_X,Bernardo,_Y,_Z,_U],white):-isBarber(Bernardo). 
barbersWigColor([Benito,_X,_Y,_Z,_U],gray):-isBarber(Benito). 
barbersWigColor([_X,_Y,Roberto,_Z,_U],red):-isBarber(Roberto). 
barbersWigColor([_X,_Y,_Z,Ramano,_U],brown):-isBarber(Ramano). 

whatWearsTheBarber(Color):-seville(X),barbersWigColor(X,Color). 

根據上述定義SWI快速返回：

?- seville(X). 
X = [[0, 0], [1, 0], [1, 1], [0, 0], [0, 0]] ; 
X = [[0, 0], [1, 0], [1, 1], [0, 0], [1, 0]] ; 
X = [[0, 0], [1, 0], [1, 1], [0, 0], [0, 0]] ; 
X = [[1, 1], [0, 0], [1, 0], [0, 0], [0, 0]] ; 
X = [[1, 0], [0, 0], [1, 1], [0, 0], [0, 0]] ; 
false. 


?- whatWearsTheBarber(Color). 
Color = red ; 
Color = red ; 
Color = red ; 
Color = gray ; 
Color = red ; 
false. 

我不太瞭解事實5的工作原理。我不能排除貝尼託是理髮師的情況。但我想發佈這個答案。

Answer 2

作爲「答案」發帖只是因爲它很長的評論。這是我第一次用prolog嘗試過這樣的東西。我不確定我對/ 1的使用是否正確。這兩個（！）答案給出了白色和棕色（儘管棕色將被排除，我認爲，如果事實4意味着伯納德不能成爲理髮師）。註釋掉的部分導致無限遞歸。

person(bernardo). 
person(benito). 
person(roberto). 
person(ramano). 
person(alfredo). 

opposite(bernardo, benito). % fact 1 
opposite(benito, bernardo). % fact 1 
opposite(roberto, ramano). % fact 2 
opposite(ramano, roberto). % fact 2 
opposite(X, Y):- dif(X, Y). % cannot be opposite to yourself 
%opposite(X, Y):- opposite(Y, X). % symmetric 

wears(alfredo, black). 
wears(bernardo, white). 
wears(benito, gray). 
wears(roberto, red). 
wears(ramano, brown). 

follower(A, A). 
follower(bernardo, alfredo). % fact 4 
follower(ramano, alfredo):- % fact 3 
    follower(alfredo, benito); follower(benito, alfredo). 
follower(ramano, benito):- % fact 3 
    follower(alfredo, benito); follower(benito, alfredo). 
follower(X, ramano):- % fact 3 
    follower(X, alfredo); follower(X, benito). 
%follower(A, B):- 
% dif(A, B), 
% person(X), 
% follower(A, X), 
% follower(X, B). 

follower(A, B):- not(opposite(A, B)). 
follower(B, A):- not(opposite(A, B)). 

fact5(Barber):-                 
    not(follower(bernardo, X));             
    not(follower(bernardo, alfredo));            
    person(X),                  
    person(Y),                  
    follower(Barber, X),               
    dif(Y, X),                  
    not(follower(Barber, Y)).              

whatWearsTheBarber(WigColor):-             
    person(Barber), % implicit in question?          
    dif(alfredo, Barber), % fact 4             
    follower(bernardo, Barber), % fact 4           
    fact5(Barber),                 
    wears(Barber, WigColor).