4

レイモンド・スマリヤンの「モッキンバードをあざける」を読んでいます。この本には、次のようなパズルがあります。

この物語のセビリアとスペインの有名なセビリア (実際には存在しない) との類似点は、まったくの偶然です。この神話の町セビリアでは、男性の住民は気分が良い日だけかつらを着用します。一日中同じように振る舞う住民は 2 人もいません。つまり、男性が 2 人いる場合、そのうちの 1 人がかつらを着用し、もう 1 人が着用しない日が少なくとも 1 日はあるということです。男性の居住者 X および Y が与えられた場合、X が着用するすべての日、Y がかつらを着用する場合、居住者 Y は X の信奉者であると言われます。また、居住者 X、Y、および Z が与えられた場合、X と Y の両方が着用するすべての日に Z がかつらを着用する場合、居住者 Z は X および Y のフォロワーであると言われます。

住民のうち 5 人の名前は、アルフレッド、ベルナルド、ベニート、ロベルト、ラマノです。それらについて次の事実が知られています。

事実 1.. ベルナルドとベニートは、かつらをかぶる習慣が正反対です。つまり、いつでも、1 人はかつらを着用し、もう 1 人はかつらを着用していません。

事実 2: ロベルトとラマノも正反対です。

事実 3: ラマノは、アルフレドとベニートの両方がかつらを着用している日だけかつらを着用します.

セビリアにはちょうど 1 人の理髪師がいて、彼について次の事実が知られています。

事実 4: ベルナルドはアルフレッドと床屋の信奉者です。

事実 5: 男性の住民 X が与えられた場合、ベルナルドがアルフレドと X の信奉者である場合、理髪師は X のみの信奉者です。

アルフレドは黒のかつらのみを着用しています。ベルナルドは白いかつらだけを着用しています。ベニートは灰色のかつらのみを着用しています。ロベルトは赤いかつらのみを着用しています。ラマノは茶色のかつらのみを着用しています.

あるイースターの朝、理髪師がかつらをかぶっているのが見られました。彼は何色の服を着ていましたか?

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: まず、Roberto が床屋のフォロワーであることを証明します。

理髪師がかつらを着用する日を考えてみましょう。その日、アルフレドはかつらをかぶるか、かぶらないかのどちらかです。Alfredo がそうだとしましょう。ベルナルドはアルフレドと床屋の信奉者であるため、その日はベルナルドもかつらを着用します。その日、ベニートはベルナルドとは反対なので、かつらをかぶることはできません。その日、ラマノはかつらをかぶることができません。アルフレドとベニートの両方がかつらを着用している日だけかつらを着用し、ベニートはこの日はかつらを着用していないからです。この日、ラマノはかつらをかぶらないので、ロベルトはラマノとは反対なので、ロベルトはかつらをかぶる必要があります. これは、床屋がかつらを着用する日はいつでも、アルフレドもかつらを着用する場合、ロベルトも着用することを証明しています.

では、理髪師がかつらをかぶっていて、アルフレードがかぶっていない日はどうでしょうか? まあ、アルフレドはそうではないので、アルフレドとベニートの両方がそうであるというわけではありません。したがって、事実 3 により、ラマノはかつらを着用せず、したがって事実 2 によりロベルトは着用します。したがって、ロベルトは床屋が行う日はいつでもかつらを着用し、アルフレドは実際には着用しません。彼は、アルフレドが着用しないすべての日にかつらを着用します。 t、床屋に関係なく。これは、床屋がかつらを着用する日はいつでも、その日にアルフレドがかつらを着用するかどうかに関係なく、ロベルトも着用することを証明しています. したがって、ロベルトは確かに理髪師の信奉者です。

4

2 に答える 2

5

Edit2: @killy9999 が本からソリューションの一部を投稿したので、Smullyan の推論を反映できるように Prolog を書き直すことにしました。元の部分解は以下に保持されます。

最初にいくつかの基本的な構造

 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]).

次に、2 種類の整合性条件があります。1つは、相手が同時にかつらを着用することは決してないという事実から導き出されます. もう 1 つは、事実 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).

これは、Roberto が Barber に従うことを証明するのに十分です (ステップ 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) では、Fact 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].

アンドリュー・クックに感謝します。私は彼の答えから借りました。

以下のテキストは、最初に投稿され、コメントが作成された回答です。


編集:特定のイースターだけでなく、何日も追跡しなければならないため、パズルは実際には非常に困難です。次の解決策は、その特定の日のみのセビリアの状況を考慮することで、検索を大幅に削減します。

セビリア市の状況を、リストとして表される未知の関係と考える方が簡単かもしれません。

 [ [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 の仕組みがよくわかりません。そして、ベニートが床屋である可能性も否定できません。それでも、これを回答として投稿したいと思います。

于 2012-04-22T15:35:07.827 に答える
1

コメントが長いという理由だけで「回答」として投稿します。プロローグでこのようなことを試したのはこれが初めてです。not/1 の使用が正しいかどうかわかりません。2つの(!)答えとして白と茶色を与えます(ただし、事実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). 
于 2012-04-22T14:37:20.810 に答える