11

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.

1
  • Did I get that right: one is a criminal, but three are liars?!
    – ThomasH
    Dec 21, 2009 at 12:44

5 Answers 5

25

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.
3
  • What if the criminals can be two of a,b,c,d?
    – user198729
    Dec 23, 2009 at 3:33
  • @user198729: Then end the clause with A+B+C+D=:=1;A+B+C+D=:=2. Jun 20, 2010 at 11:27
  • @CharlesStewart I'm not so sure. By adding A+B+C+D=:=2 in this way you are only allowing that two individuals tell the truth, not that two are criminals. You might need more information to solve this, e.g. such that everybody makes statements about two individuals, not just one.
    – ThomasH
    Mar 25, 2019 at 10:37
21

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.

8

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.
3

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)).
3

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.

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.