Take the 2-minute tour ×

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.

share|improve this question
Did I get that right: one is a criminal, but three are liars?! –  ThomasH Dec 21 '09 at 12:44
add comment

5 Answers

up vote 18 down vote accepted

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 ;
share|improve this answer
+1 This is interesting. –  ThomasH Dec 21 '09 at 22:15
What if the criminals can be two of a,b,c,d? –  user198729 Dec 23 '09 at 3:33
@user198729: Then end the clause with A+B+C+D=:=1;A+B+C+D=:=2. –  Charles Stewart Jun 20 '10 at 11:27
add comment

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:


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.

share|improve this answer
add comment

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),
        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 ;
share|improve this answer
add comment

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


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

share|improve this answer
Please don't provide link only answers, write something more. –  Cristian Ciupitu May 5 '13 at 9:50
add comment

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

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

solve(TruthTeller) :-
    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)).
share|improve this answer
add comment

Your Answer


