Whodunit: Difference between revisions

Revision as of 18:54, 5 January 2017

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

@@ Line 16: / Line 16: @@
 ==== solve_murder( ?Murderer ) ====
 Solving the crime means finding the <var>Murderer</var>'s identity, such that the <var>Murderer</var>'s statement is the only one that is inconsistent with the statements of the other suspects.
-<syntaxhighlight lang="prolog">solve_murder( Murderer ) :-
+<pre class="prolog">solve_murder( Murderer ) :-
-     unique_solution( murderer( Murderer ) ).</syntaxhighlight>
+     unique_solution( murderer( Murderer ) ).</pre>
 Firstly, the suspects' statements are formalized:
-<syntaxhighlight lang="prolog">statement( a ) --> [innocent(a),friend(b,m),hates(c,m)].
+<pre class="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)].
@@ Line 26: / Line 26: @@
 statements( [Witness|Witnesses] ) -->
      statement( Witness ),
-     statements( Witnesses ).</syntaxhighlight>
+     statements( Witnesses ).</pre>
 Then we define mutual-exclusivity between assertions.
-<syntaxhighlight lang="prolog">mutually_exclusive( [friend(X,Y), hates(X,Y), not_know(X,Y)] ).
+<pre class="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>
+mutually_exclusive( [alibi(X), guilty(X)] ).</pre>
 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 ) :-
+<pre class="prolog">murderer( Murderer ) :-
      Suspects = [a,b,c],
      select( Murderer, Suspects, Witnesses ),
      phrase( statements(Witnesses), Assertions ),
-     consistent( [guilty(Murderer)|Assertions] ).</syntaxhighlight>
+     consistent( [guilty(Murderer)|Assertions] ).</pre>
 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 ) :-
+<pre class="prolog">consistent( Statements ) :-
-     \+ inconsistent( Statements ).</syntaxhighlight>
+     \+ inconsistent( Statements ).</pre>
 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] ) :-
+<pre class="prolog">inconsistent( [Assertion|Assertions] ) :-
      mutually_exclusive( Exclusive ),
      select( Assertion, Exclusive, Inconsistent ),
@@ Line 49: / Line 49: @@
      member( Inconsistency, Assertions ).
 inconsistent( [_Assertion|Assertions] ) :-
-     inconsistent( Assertions ).</syntaxhighlight>
+     inconsistent( Assertions ).</pre>
 Load a small library of [[Puzzle Utilities]].
-<syntaxhighlight lang="prolog">
+<pre class="prolog">:- ensure_loaded( misc ).</pre>
-:- ensure_loaded( misc ).
-</syntaxhighlight>
 The code is available as plain text [http://www.binding-time.co.uk/download/whodunit.txt here].