Решение логической загадки с помощью Пролога
Преступник является одним из A, B, C и D.
Говорить: "Это не я"
B говорит: "Это - D"
C говорит: "Это - B"
D говорит: "Это не я"
И мы знаем, что только один из них говорит правду.
Кто тот? Я хочу решить его при помощи Пролога.
Это - вопрос об интервью.
3 ответа
Однострочное решение
?- 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.
Disclaimer: Это решение 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 является правдивым, в противном случае нет. Асф. То есть переменные A, B, ... отражают правдивость ответчика, если он является конкретным преступником.
Поскольку известным ограничением является тот факт, что только один из них является правдивым, сумма их истинных значений должна быть равна 1. Отступая, Пролог делает следующую привязку для K, и пробегает через нее снова. Оказывается, ограничение удовлетворяется только в том случае, если a является преступником (и d говорит правду, если я не ошибаюсь). Мило.
Вот еще одно решение, которое я нахожу немного менее загадочным, чем у 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.