/* Whodunit? Problem posted to comp.lang.prolog by Nimesh777@aol.com
 *
 * Problem Statement:
 *
 * M has been murdered. A, B and C are suspects.
 * A says he is innocent, B was M's friend but C hated M.
 * B says that he was out of town on the day of the murder, besides he
 * didn't even know M.
 * C says he is innocent but he saw A & B with M just before the murder.
 *
 * Assuming that all except possibly the murderer are telling the truth,
 * solve the crime.
 */

/* Solving the crime means finding a single solution to the murderer's
 * identity.
 */
solve_murder( Murderer ) :-
    single_solution( murderer( Murderer ) ).

/* Firstly, the suspects' statements are formalized:
 */
statement( a ) --> [innocent(a),friend(b,m),hates(c,m)].
statement( b ) --> [alibi(b),not_know(b,m)].
statement( c ) --> [innocent(c),with(c,m),with(b,m),with(a,m)].

statements( [] ) --> [].
statements( [Witness|Witnesses] ) -->
	statement( Witness ),
	statements( Witnesses ).

/* Then we define pairwise exclusivity between assertions.
 */
pairwise_exclusive( [friend(X,Y), hates(X,Y), not_know(X,Y)] ).
pairwise_exclusive( [innocent(X), guilty(X)] ).
pairwise_exclusive( [alibi(X), with(X,m)] ).
pairwise_exclusive( [alibi(X), with(m,X)] ).
pairwise_exclusive( [alibi(X), guilty(X)] ).

/* A murderer is identified by showing that the statements of the other
 * suspects (witnesses) are consistent with each other, and with the
 * murderer being guilty.
 */
murderer( Murderer ) :-
	Suspects = [a,b,c],
	select( Murderer, Suspects, Witnesses ),
	phrase( statements(Witnesses), Assertions ),
	consistent( [guilty(Murderer)|Assertions] ).

/* A set of assertions is consistent if no inconsistency can be found
 * between any member and the rest of the set.
 */
consistent( Statements ) :-
	forall(
		select( Statement, Statements, Rest ),
		\+ inconsistent( Statement, Rest )
		).

/* An assertion is inconsistent with a set of assertions if it is pairwise
 * exclusive with a member of the set.
 */
inconsistent( Assertion,  Assertions ) :-
	pairwise_exclusive( Exclusive ),
	select( Assertion, Exclusive, Inconsistent ),
	member( Inconsistency, Inconsistent ),
	member( Inconsistency, Assertions ).

:- ensure_loaded( misc ).