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. <syntaxhighlight lang="prolog">solve_murder( Murderer ) :-

   unique_solution( murderer( Murderer ) ).</syntaxhighlight>

Firstly, the suspects' statements are formalized: <syntaxhighlight lang="prolog">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 ).</syntaxhighlight>

Then we define mutual-exclusivity between assertions. <syntaxhighlight lang="prolog">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)] ).</syntaxhighlight> 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. <syntaxhighlight lang="prolog">murderer( Murderer ) :-

   Suspects = [a,b,c],
   select( Murderer, Suspects, Witnesses ),
   phrase( statements(Witnesses), Assertions ),
   consistent( [guilty(Murderer)|Assertions] ).</syntaxhighlight>

A set of assertions is consistent if no inconsistency can be found between any member and the rest of the set. <syntaxhighlight lang="prolog">consistent( Statements ) :-

   \+ inconsistent( Statements ).</syntaxhighlight>

An assertion is inconsistent with a set of assertions if it is pairwise exclusive with a member of the set. <syntaxhighlight lang="prolog">inconsistent( [Assertion|Assertions] ) :-

   mutually_exclusive( Exclusive ),
   select( Assertion, Exclusive, Inconsistent ),
   member( Inconsistency, Inconsistent ),
   member( Inconsistency, Assertions ).

inconsistent( [_Assertion|Assertions] ) :-

   inconsistent( Assertions ).</syntaxhighlight>

Load a small library of Puzzle Utilities.

<syntaxhighlight lang="prolog">

- ensure_loaded( misc ).

</syntaxhighlight>

The code is available as plain text here.

Result

?- solve_murder( Murderer ).
Murderer = b