# Whodunit

## Problem Statement

Problem posted to comp.lang.prolog by Nimesh777@aol.comM 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