MrPandMrS

このプログラムは、ドイツの Karlsruhe で行なわれた International Joint Conference on Artificial Intelligence 83 で、 Martin Nilsson が発表した有名な 'Mr. P and Mr. S problem' 問題を解決するプログラムです。

この問題は以下の通りです。

  ある人が、1 から 100 までの自然数から2つの数を頭の中で思い浮かべます。
  その人は、その2数の和をSさんに、2数の積をPさんにそれぞれ伝えます。
  そして、以下のように対話が行なわれます。

        Mr. P:  2数がそれぞれ何かわかりません。
        Mr. S:  私もわかりません。でも私は、あなたがそれをわからないであろう
                ということはわかっています。
        Mr. P:  あっそうですか。それならば、その2数はわかります。
        Mr. S:  あっそう? それならば、私もわかります。

  問題はもちろん、「2つの数は一体何と何でしょうか?」というものです。

この Nilsson のプログラムは、基礎的なPrologの特徴を組み合わせて 力を発揮するとても美しい例です。

ある人が、2番めの人の知識を知っているということを表現するメタ述語と ちからまかせの探索を行なうことによって、問題を解くのです。

以下にソースコードを紹介します。 (スタンドアローンプログラムとして構成されています。):

main(_) :- ps.
program :- ps.

ps  :- w(o1,_,X), write(X), nl.

w(s1,(I,J),(M,N)) :-
	for(2,M,99),for(2,N,M),
	M+N =:= I+J.
w(p1,(I,J),(M,N)) :-
	for(2,M,99),
	for(2,N,M),
	M*N =:= I*J.
w(s2,S,X) :- w(s1,S,X),p3(X).
w(p2,S,X) :- w(p1,S,X),p4(X).
w(s3,S,X) :- w(s2,S,X),p5(X).
w(o1,_,(M,N)) :-
         for(2,M,99),for(2,N,M), write((M,N)),nl,
         p3((M,N)), write(p3),nl,
	 p4((M,N)), write(p4),nl,
	 p5((M,N)), write(p5),nl,
	 p6((M,N)), write(p6),nl.
p3(X) :- has_two_or_more_solutions(w(p1,X,_)).
p4(X) :- has_two_or_more_solutions(w(s2,X,_)),
         all_in_are(Z, (w(s1,X,W),value(p3(W),Z)),true).
p5(X) :- has_exactly_one_solution(w(p2,X,_)).
p6(X) :- has_exactly_one_solution(w(s3,X,_)).

value(X,V) :- (X, V=true; V=false),!.
all_in_are(X,G,Z) :- \+ ((G,X \= Z)),!.
has_exactly_one_solution(X) :- copy_term(X,X2),X,all_in_are(X2,X2,X), !.
has_two_or_more_solutions(X) :- copy_term(X,X2),X,!,X2,X \= X2,!.