Решение логической головоломки с использованием Пролога - PullRequest
Новая
       16

Решение логической головоломки с использованием Пролога

10 голосов
/ 21 декабря 2009

Преступник - один из А, В, С и D.

А говорит: "Это не я"
Б говорит: «Это Д»
С говорит: «Это Б»
Д говорит: «Это не я»

И мы знаем, что только один из них говорит правду.

Кто это? Я хочу решить это с помощью Пролога.

Это вопрос интервью.

Ответы [ 5 ]

24 голосов
/ 21 декабря 2009

Однострочное решение 

?- 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.
20 голосов
/ 22 декабря 2009

Отказ от ответственности : Это решение 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. При возврате, Пролог делает следующее связывание для K и снова проходит через него. Оказывается, ограничение выполняется только в том случае, если a является преступником (а d говорит правду, если я не ошибаюсь). Cute.

8 голосов
/ 28 декабря 2009

Вот еще одно решение, которое я нахожу немного менее загадочным, чем у 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.
3 голосов
/ 19 декабря 2011

Я столкнулся с этой проблемой и хотел дать ей шанс: 

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)).
2 голосов
/ 21 апреля 2011

Аналогичная проблема и соответствующее решение также можно найти здесь:

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

Как и решение, опубликованное Kaarel, можно запросить обоснование / объяснение найденного решения.

...