Solving a logic puzzle using Prolog

Question

The criminal is one of A, B, C and D.

A says: "It's not me"
B says: "It's D"
C says: "It's B"
D says: "It's not me"

And we know that only one of them tells the truth.

Who is the one? I want to solve it by using Prolog.

It's an interview question.

Answer 1

Disclaimer: This is Xonix' solution. If you like it vote him up. But as it took me some head-scratching to figure out what was going on, I thought I might just as well offer my comments so others could benefit.

At first, here is his solution as a proper clause:

criminal(K):-
    member(K,[a,b,c,d]),
    (K\=a -> A=1;A=0),
    (K=d  -> B=1;B=0),
    (K=b  -> C=1;C=0),
    (K\=d -> D=1;D=0),
    A+B+C+D=:=1.

And it goes like this:

At first, he runs through the list of individuals (have to be lower case, so they're not variables). K is instantiated to each of them in turn.

With each possible value of K he runs through the rest of the clause. K can be interpreted as the hypothesis who the criminal is. The next 4 lines are to provide bindings to each of the variables A, B, C and D. You can read them like this: Under the assumption that a is not the criminal, a is truthful otherwise not. Under the assumption that d is the criminal, b is truthful otherwise not. Asf. That is, the variables A, B, ... capture the truthfulness of the corrsponding individual, given a specific criminal.

As a known constraint is the fact that only one of them is truthful, the sum of their truth values must be 1. On backtracking, Prolog makes the next binding for K, and runs through it again. Turns out the constraint is only satisfied if a is the criminal (and d is telling the truth, if I'm not mistaken). Cute.

Answer 2

I ran across this problem and wanted to give it a shot :

a(K) :- K \== a.
b(d).
c(b).
d(K) :- K \== d.

solve(TruthTeller) :-
    member(K, [a, b, c, d]),
    xor([a(K), b(K), c(K), d(K)], Truth),
    Truth =.. [TruthTeller|_].

xor([Head|Tail], Result) :-
    (   call(Head)
     -> forall(member(X, Tail), \+ call(X)), Result = Head
     ;  xor(Tail, Result)).

Answer 3

Here is another solution which I find a bit less cryptic than Xonix's. Tested in SWI-Prolog.

% To find a criminal and the truthteller
% 1. Pick a possible criminal
% 2. Pick a possible truthteller and the remaining liars
% 3. Assert that the truthteller's statement is the truth
% 4. Assert that every liar's statement is not the truth
% If both the assertions succeed
% then we have found a criminal and the truthteller.
criminal_and_truthteller(Criminal, Truthteller) :-
    Group = [a, b, c, d],
    member(Criminal, Group),
    select(Truthteller, Group, Liars),
    statement(Truthteller, Criminal, Truth),
    Truth,
    forall(
        member(Liar, Liars),
        (statement(Liar, Criminal, Lie), \+ Lie)
    ).

% Statements
% Arg 1: Who says
% Arg 2: About whom
% Arg 3: Which statement
% e.g. "a claims that a is not a criminal"
statement(a, C, a \= C).
statement(b, C, d  = C).
statement(c, C, b  = C).
statement(d, C, d \= C).

Usage example:

?- criminal_and_truthteller(Criminal, Truthteller).
Criminal = a,
Truthteller = d ;
false.

Answer 4

One-liner solution

?- member(K,[a,b,c,d]),(K\=a->A=1;A=0),(K=d->B=1;B=0),(K=b->C=1;C=0),(K\=d->D=1;D=0),A+B+C+D=:=1.
K = a,
A = 0,
B = 0,
C = 0,
D = 1 ;
false.

Answer 5

A similar problem and corresponding solution can also be found here:

https://github.com/LogtalkDotOrg/logtalk3/blob/master/examples/puzzles/jam_thief.lgt

Like the solution posted by Kaarel, is possible to request a justification/explanation for the solution found.