[Перевод] Ищем убийцу на Прологе

Каждое воскресенье в нашей компании принято устраивать весёлые викторины, это одна из них.
Чтобы найти убийцу мистера Бодди, нужно узнать, где находился каждый человек и какое оружие было в комнате. Подсказки разбросаны по всей викторине (вы не можете ответить на первый вопрос, пока не прочитаете все десять).

• Для начала, представим подозреваемых. Есть три мужчины (Джордж, Джон, Роберт) и три женщины (Барбара, Кристина, Иоланда). Каждый человек находится в отдельной комнате (ванная, столовая, кухня, гостиная, кладовая, кабинет). В каждой комнате найдено подозрительное оружие (сумка, огнестрельное оружие, газ, нож, яд, верёвка). Вопрос: кого нашли на кухне?
• Подсказка 1. При мужчине на кухне нет ни верёвки, ни ножа, ни сумки. Оружие не является огнестрельным. Вопрос: какое оружие найдено на кухне?

• Подсказка 2. Барбара либо в кабинете, либо в ванной, а Иоланда — в другой комнате из двух названных. В какой комнате нашли Барбару?
• Подсказка 3. Человек с сумкой — это ни Барбара, ни Джордж, и он не был ни в ванной, ни в столовой. У кого была сумка?
• Подсказка 4. Женщина с верёвкой найдена в кабинете. Кто это?
• Подсказка 5. Оружие в гостиной принадлежит либо Джону, либо Джорджу. Какое оружие в гостиной?
• Подсказка 6. Ножа не было в столовой. Где был нож?
• Подсказка 7. Иоланды не было ни в кабинете, ни в кладовой с соответствующим оружием для этих комнат. Какое оружие у Иоланды?
• Подсказка 8. У Джорджа найдено огнестрельное оружие. В какой комнате?
• Было обнаружено, что мистера Бодди отравили газом в кладовой. Подозреваемый в той комнате был убийцей. Кто же это?

Я тащусь от таких головоломок (вообще-то почти от любых головоломок). Они могли бы занять часы и часы размышлений, но всегда на помощь приходит Prolog! Посмотрим, как он помогает решить такие задачи на рассуждения.

Установка SWI-Prolog

~> swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- write('Hello, World!').
Hello, World!
true.
?- write('Hello,'), nl, write('world').
Hello,
world
true.
?- X is 3*4 + 2.
X = 14.

• swipl — программа-интерпретатор Prolog
• write называется функтором, а представление write/1 означает, что он принимает 1 аргумент (та же концепция в Erlang и Elixir для добавления количества аргументов к имени функции)
• nl используется для печати новой строки
• последовательность команд разделяется запятыми, которые также заменяют оператор AND
• за оператором присвоения is следует математическое выражение
• переменные пишутся заглавными X, а не x

База знаний

Суть Prolog — в констатации фактов, составлении фактов и их запросе.

Создание файла hello.pl:

friend(john, julia).
friend(john, jack).
friend(julia, sam).
friend(julia, molly). loves(john, julia).
loves(julia, sam).
loves(sam, julia). male(brad).
male(john).
male(jim).
male(alfred).
female(marry).
child(brad, alfred).
child(john, jim).
child(john, marry).

• для загрузки используем [hello].: обратите внимание на точку в конце
• listing перечисляет все факты в базе знаний

?- [hello].
% hello compiled 0.00 sec, 3 clauses
true. ?- listing(friend).
friend(john, julia).
friend(john, jack).
friend(julia, sam).
friend(julia, molly). true. ?- listing(loves).
loves(john, julia).
loves(julia, sam).
loves(sam, julia). true.

Запрос фактов

После изложения фактов в базе знаний можем пойти дальше и задавать вопросы об истинности фактов, а также о том, какие выводы можно из них сделать.

?- friend(john, julia).
true . ?- friend(john, jack).
true. ?- loves(john, julia).
true. ?- loves(john, sam).
false.

Можем составлять и более сложные вопросы. Например, кто дружит с Джоном или кто любит Джулию.

?- friend(john, Who).
Who = julia ;
Who = jack.

?- listing(child).
child(brad, alfred).
child(john, jim).
child(john, mary). true. ?- child(john, X).
X = jim ;
X = mary.

Джон во френдзоне?

Мы установили дружественные отношения Джона с Джулией (friend(john, julia)), но для Prolog это не значит, что Джулия дружит с Джоном: нужно добавить ещё один факт friend(julia, john). Также мы уже указали, у кого какие дети, и явно не хотим дублировать код, отдельно указывая родителей каждого ребёнка. Мы не хотим писать что-то вроде

child(brad, alfred).
child(john, jim).
child(john, mary). parent(alfred, brad).
parent(jim, john).
parent(mary, john).

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

rule :- stmt1, stmt2,...

Правило истинно, если все внутренние утверждения истинны (перечислены и логически сложены через запятую).

friend(X, Y) :- friend(Y,X).
parent(X, Y) :- child(Y,X).
father(X, Y) :- child(Y,X), male(X).
mother(X, Y) :- child(Y,X), female(X).
friendzoned(X) :- loves(X, Y), \+ loves(Y,X).

• правило friend(X,Y) справедливо при friend(Y,X)
• parent(X,Y) справедливо при установленном child(Y,X)
• father(X,Y) справедливо при установленных parent(X,Y) и male(X)
• mother(X,Y) справедливо при установленных parent(X,Y) и female(X)
• friendzoned(X) справедливо, если X любит SOMEONE Y, а Y не любит X (заметили скрытую переменную Y?)

?- friend(julia, john).
true .
?- male(jim).
true. ?- parent(jim,X).
X = john. ?- father(jim, X).
X = john. ?- mother(X, john).
X = marry. ?- mother(marry,X).
X = john. ?- mother(marry, john).
true. ?- loves(julia, X).
X = sam. ?- friendzoned(julia).
false. ?- friendzoned(john).
true.

Хорошо, теперь у нас есть все необходимые знания. Потренируемся на раскраске карты.
Начнём с известной математической проблемы. Требуется, чтобы ни у каких смежных областей не было одинакового цвета.

Поэтому рассуждения должны быть такие, у нас есть три вещи:

1. Переменные — области, которые мы хотим раскрасить: A, B, С, D, Е.
2. Домен — диапазон значений, которые можно присвоить переменным: красный, синий, зелёный.
3. Ограничение, что смежные области не могут быть одинакового цвета.

Домен

Определим домен наших областей (красный, зелёный, синий).

color(red).
color(green).
color(blue).

Это всё.

Спрашиваем решение

colorify(A,B,C,D,E) :- color(A), color(B), color(C), color(D), color(E), \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.

Здесь мы определяем решение как правило colorify с пятью переменными А, B, С, D, Е, а внутри правила назначаем доменный цвет (красный, синий, зелёный) для переменных и устанавливаем ограничения, что А не равно B, не равно С… и т. д.

\+ X=Y означает, что X не равно Y

Prolog продолжит генерировать значения, пока не найдёт вариант, удовлетворяющий правилу с учётом ограничений.

?- [mapcoloring]
| .
true. ?- colorify(A,B,C,D,E)
| .
A = red,
B = D, D = green,
C = E, E = blue ;
A = red,
B = D, D = blue,
C = E, E = green ;
A = green,
B = D, D = red,
C = E, E = blue ;
A = green,
B = D, D = blue,
C = E, E = red ;
A = blue,
B = D, D = red,
C = E, E = green ;
A = blue,
B = D, D = green,
C = E, E = red

color(red).
color(green).
color(blue). colorify(A,B,C,D,E) :- color(A), color(B), color(C), color(D), color(E), \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.

… но мы здесь не картинки раскрашиваем, а ищем убийцу.

Убийство

Для начала, представим подозреваемых. Есть три мужчины (Джордж, Джон, Роберт) и три женщины (Барбара, Кристина, Иоланда). Каждый человек находится в отдельной комнате (ванная, столовая, кухня, гостиная, кладовая, кабинет). В каждой комнате найдено подозрительное оружие (сумка, огнестрельное оружие, газ, нож, яд, верёвка).

Кого нашли на кухне?

Домен

Из этого можно сделать вывод, что у нас пять доменов: man, woman, person или подозреваемый, location и weapons, а наши переменные (A, B, C, D, E, F) должны представлять и человека, и место, и оружие с некоторыми ограничениями, которые будут выявлены в предстоящих подсказках.

man(george). man(john). man(robert).
woman(barbara). woman(christine). woman(yolanda).
person(X):- man(X).
person(X):- woman(X).
location(bathroom). location(dining). location(kitchen). location(livingroom). location(pantry). location(study).
weapon(bag). weapon(firearm). weapon(gas). weapon(knife). weapon(poison). weapon(rope).

Правило uniq_ppl генерирует уникальные значения для наших переменных.

uniq_ppl(A,B,C,D,E,F):- person(A), person(B), person(C), person(D), person(E), person(F), \+A=B, \+A=C, \+A=D, \+A=E, \+A=F, \+B=C, \+B=D, \+B=E, \+B=F, \+C=D, \+C=E, \+C=F, \+D=E, \+D=F, \+E=F.

Решение

Мы начинаем с определения правила убийцы с уникальными людьми в местах и уникальных людей, имеющих оружие, и теперь будет указывать отношение между людьми в местах с теми, кто имеет оружие

Обратите внимание, что у нас по-прежнему шесть подозреваемых.

Вступление

murderer(X) :- uniq_ppl(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study), uniq_ppl(Bag, Firearm, Gas, Knife, Poison, Rope),

Чтобы легко рассуждать о переменных, таких как ванная, столовая, огнестрельное оружие, газ, мы сразу определяем:

• Ванная — оно же подозреваемый (мужчина или женщина) в ванной
• Огнестрельное оружие — оно же подозреваемый (мужчина или женщина) с огнестрельным оружием
• и так далее… можете представить это как решётку

Теперь продолжаем добавлять ограничения после последней запятой в правиле murderer.

Подсказка 1

При мужчине на кухне нет верёвки, ножа или сумки. Оружие не является огнестрельным. Какое оружие найдено на кухне?

% 2. Clue 1: The man in the kitchen was not found with the rope, knife, or bag.
% Which weapon, then, which was not the firearm, was found in the kitchen? man(Kitchen), \+Kitchen=Rope, \+Kitchen=Knife, \+Kitchen=Bag, \+Kitchen=Firearm,

Здесь мы говорим, что переменная Kitchen удовлетворяет факту man (определено в нашем домене), и заявляем, что кем бы ни был человек на кухне, у него нет ничего из перечисленного: Rope, Knife, Bag, Firearm.

Подсказка 2

Подсказка 2. Барбара либо в кабинете, либо в ванной, а Иоланда — в другой комнате из двух названных. В какой комнате нашли Барбару?

Таким образом, мы можем сказать, что woman есть и в кабинете, и в ванной, И это не Кристина, а также вычёркиваем остальные варианты для Барбары и Иоланды (кухня, столовая, гостиная, кладовая).

% % 3. Clue 2: Barbara was either in the study or the bathroom; Yolanda was in the other.
% % Which room was Barbara found in? woman(Bathroom), woman(Study), \+christine=Bathroom, \+christine=Study, \+barbara=Dining, \+barbara=Kitchen, \+barbara=Livingroom, \+barbara=Pantry,

Подсказка 3

Человек с сумкой — это ни Барбара, ни Джордж, и он не был ни в ванной, ни в столовой. У кого была сумка?

% % 4. Clue 3: The person with the bag, who was not Barbara nor George, was not in the bathroom nor the dining room.
% % Who had the bag in the room with them? \+barbara=Bag, \+george=Bag, \+Bag=Bathroom, \+Bag=Dining,

Подсказка 4

Женщина с верёвкой найдена в кабинете. Кто это?

% % 5. Clue 4: The woman with the rope was found in the study.
% % Who had the rope? woman(Rope), Rope=Study,

Подсказка 5

Подсказка 5. Оружие в гостиной принадлежит либо Джону, либо Джорджу. Какое оружие в гостиной?

man in Livingroom
Livingroom isn’t robert
% % 6. Clue 5: The weapon in the living room was found with either John or George.
% % What weapon was in the living room? man(Livingroom), \+Livingroom=robert,

Подсказка 6

Ножа не было в столовой. Где был нож?

% % 7. Clue 6: The knife was not in the dining room.
% % So where was the knife? \+Knife=Dining,

Подсказка 7

Подсказка 7. Иоланды не было ни в кабинете, ни в кладовой. Какое оружие в комнате у Иоланды?

% % 8. Clue 7: Yolanda was not with the weapon found in the study nor the pantry.
% % What weapon was found with Yolanda? \+yolanda=Pantry, \+yolanda=Study,

Подсказка 8

У Джорджа найдено огнестрельное оружие.

% % 9. Clue 8: The firearm was in the room with George.
% % In which room was the firearm found? Firearm=george,

Подсказка 9

Было обнаружено, что мистера Бодди отравили газом в кладовой. Подозреваемый в той комнате был убийцей. Кто это?

% % 10. It was discovered that Mr. Boddy was gassed in the pantry. The suspect found in that room was the murderer.
% % Who, then, do you point the finger towards?
Pantry=Gas, Pantry=X, write("KILLER IS :"), write(X), nl, writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope).

Устанавливаем соответствие для газа, кладовой и убийцы, затем используем write для вывода ответов writeanswers.

writeanswers(Bathroom, Dining, Kitchen, Livingroom, Pantry, Study, Bag, Firearm, Gas, Knife, Poison, Rope):- write("Bathroom: "), write(Bathroom), nl, write("Dining: "), write(Dining), nl, write("Livingroom: "), write(Livingroom), nl, write("Pantry: "), write(Pantry), nl, write("Study: "), write(Study), nl, write("Kitchen: "), write(Kitchen), nl, write("Knife: "), write(Knife), nl, write("Gas: "), write(Gas), nl, write("Rope: "), write(Rope), nl, write("Bag: "), write(Bag), nl, write("Poison: "), write(Poison), nl, write("Firearm: "), write(Firearm), nl.

Кто убийца?

?- [crime2].
true.
?- murderer(X).
KILLER IS :christine
Bathroom: yolanda
Dining: george
Livingroom: john
Pantry: christine
Study: barbara
Kitchen: robert
Knife: yolanda
Gas: christine
Rope: barbara
Bag: john
Poison: robert
Firearm: george
X = christine ;

Код опубликован здесь. Вероятно, он мог быть намного лучше, поскольку я не эксперт в Прологе 🙂