Whodunit

Problem Statement

Problem posted to comp.lang.prolog by Nimesh777@aol.com

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.

Solution

When you have eliminated the impossible, whatever remains, however improbable, must be the truth. Sir Arthur Conan Doyle - The Sign of the Four

solve_murder( ?Murderer )

Solving the crime means finding the Murderer's identity, such that the Murderer's statement is the only one that is inconsistent with the statements of the other suspects.

solve_murder( Murderer ) :-
    unique_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 mutual-exclusivity between assertions.

mutually_exclusive( [friend(X,Y), hates(X,Y), not_know(X,Y)] ).
mutually_exclusive( [innocent(X), guilty(X)] ).
mutually_exclusive( [alibi(X), with(X,m)] ).
mutually_exclusive( [alibi(X), with(m,X)] ).
mutually_exclusive( [alibi(X), guilty(X)] ).

The 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 ) :-
    \+ inconsistent( Statements ).

An assertion is inconsistent with a set of assertions if it is pairwise exclusive with a member of the set.

inconsistent( [Assertion|Assertions] ) :-
    mutually_exclusive( Exclusive ),
    select( Assertion, Exclusive, Inconsistent ),
    member( Inconsistency, Inconsistent ),
    member( Inconsistency, Assertions ).
inconsistent( [_Assertion|Assertions] ) :-
    inconsistent( Assertions ).

Load a small library of Puzzle Utilities.

:- ensure_loaded( misc ).

The code is available as plain text here.

Result

?- solve_murder( Murderer ).
Murderer = b