使用Prolog解决逻辑谜题

Question

罪犯是A,B,C和D之一.

A说:"这不是我"
B说:"它是D"
C说:"它是B"
D说:"这不是我"

而且我们知道其中只有一个说实话.

谁是谁？我想用Prolog来解决它.

这是一个面试问题.

Answer 1

单线解决方案

?- 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 2

免责声明:这是Xonix的解决方案.如果你愿意,可以投票给他.但是,由于我要弄清楚究竟发生了什么,我想我也可以提出我的意见,以便其他人可以受益.

首先,这是他作为正确条款的解决方案:

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.

它是这样的:

首先,他浏览个人名单(必须是小写,所以他们不是变量).K依次对它们中的每一个进行实例化.

随着每个可能的价值,K他贯穿了条款的其余部分.K可以解释为罪犯的假设.接下来的4行是为每个变量A,B,C和D提供绑定.你可以这样读出它们:在a不是罪犯的假设下,a是真实的,否则不是.在假设d是罪犯的情况下,b是真实的,否则不是.ASF.也就是说,给定一个特定的罪犯,变量A,B,...捕获相应个体的真实性.

由于已知的约束是事实,其中只有一个是真实的,它们的真值的总和必须为1.在回溯时,Prolog为K做下一个绑定,并再次运行它.事实证明只有a犯罪者才会满足约束(并且d说实话,如果我没有弄错的话).可爱.

Answer 3

这是另一种解决方案,我发现它比Xonix的神秘程度要低一些.在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).

用法示例:

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