| This program solves the famous 'Mr. P and Mr. S problem' as
presented by Martin Nilsson at the International Joint Conference
on Artificial Intelligence 83 in Karlsruhe, West Germany.
The problem goes as follows:
A person thinks of two natural numbers between 1 and 100.
He tells their sum to Mr S, and their product to Mr. P.
Then the following dialogue develops:
Mr. P: I don't know the numbers.
Mr. S: I don't know them either, but I knew that
you would not know them.
Mr. P: Oh, then I know the numbers!
Mr. S: So? Then I know them, too!
The problem, of course, is: What were the two numbers?
This designer program as adapted from Nilsson is a beautiful example
of the combined power of basic Prolog features:
Meta predicates to express what one person knows about a second
persons knowledge, and brute-force search.
Here is the source (configured as standalone):
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,!.
| 
