Prolog中的"谁是理发师"逻辑谜题

Question

我正在阅读Raymond Smullyan的"嘲笑模仿鸟".在书中有一个谜题是这样的:

这个故事的塞维利亚与西班牙着名的塞维利亚(实际上没有)之间的任何相似之处纯属巧合.在这个神秘的塞维利亚小镇,男性居民戴着假发,只有他们感觉喜欢的那些日子.没有两个居民在所有日子里都表现得一样; 也就是说,如果任何两个男性居民,至少有一天他们中的一个戴着假发而另一个则不戴.鉴于任何男性居民X和Y,居民Y据说是X的追随者,如果在X所有的日子里戴假发.此外,如果居民X,Y和Z,如果Z在X和Y都做的所有日子都佩戴假发,则居民Z被称为X和Y的追随者.

其中五名居民被命名为Alfredo,Bernardo,Ben-ito,Roberto和Ramano.以下事实是关于它们的:

事实1 ......贝尔纳多和贝尼托在他们的假发习惯方面相反; 也就是说,在任何一天,其中一个戴假发,另一个戴假发.

事实2:罗伯托和拉马诺同样是对立的.

事实3:拉马诺戴着假发,只有在阿尔弗雷多和贝尼托都戴上假发的那几天.

塞维利亚只有一个理发师,以下事实是关于他的:

事实4:贝尔纳多是阿尔弗雷多和理发师的追随者.

事实5:鉴于任何男性居民X,如果Bernardo是Alfredo和X的下属,那么理发师就是X的追随者.

阿尔弗雷多只穿黑色假发; 贝尔纳多只穿白色假发; 贝尼托只穿灰色假发; 罗伯托只穿红色假发; 而Ramano只戴着棕色假发.

一个复活节早晨,理发师戴着假发.他穿的是什么颜色？

我发现在Prolog中解决这个问题会很有趣,但我很早就陷入了困境:

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步:首先,我们证明罗伯托是理发师的追随者.

好吧,考虑理发师戴假发的任何一天.要么阿尔弗雷多当天戴假发,要么他不戴假发.假设阿尔弗雷多做了.然后贝尔纳多也戴着假发,因为贝尔纳多是阿尔弗雷多和理发师的追随者.所以贝尼托当天不能戴假发,因为他与贝尔纳多相反.然后Ramano当天不能戴假发,因为他只在Alfredo和Benito都这样做的时候戴假发,Benito在这一天没戴假发.由于拉马诺在这一天没戴假发,所以罗伯托必须,因为罗伯托与拉马诺相对.这证明,在理发师戴假发的任何一天,如果阿尔弗雷多也这样做,那么罗伯托也是如此.

现在,理发师戴假发的那一天,但阿尔弗雷多不戴？好吧,既然阿尔弗雷多没有,那么阿尔弗雷多和贝尼托都不会这样做; 因此事实3,Ramano没有,事实上罗伯托也没有.所以罗伯托在理发师做的任何一天戴着假发,而阿尔弗雷多没有 - 事实上,他在阿尔弗雷多所做的所有日子都戴着假发. t,不管理发师.这证明,在理发师戴假发的任何一天,罗伯托也会这样做,无论Alfredo当天是否戴假发.罗伯托确实是理发师的追随者.

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步)贝尔纳多跟随罗伯托和阿尔弗雷多:

 ?- 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查询显示RED是唯一的答案

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

感谢Andrew Cooke.我借鉴了他的答案.

下面的文字是最初发布的答案,并产生了评论.

编辑:这个难题实际上非常困难,因为人们必须记录很多天,而不仅仅是特定的复活节.以下解决方案通过仅在特定日期考虑塞维利亚的事态来大大减少搜索.

可能更容易将塞维利亚市的情况视为一个未知的关系,表示为一个列表:

 [ [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是如何运作的.当贝尼托是理发师时,我不能排除这种情况.但我想发布这个作为答案.