Every Sunday in our company it is customary to arrange fun quizzes, this is one of them.

Riddle

To find the murderer of Mr. Boddy, you need to find out where each person was and what weapon was in the room. Clues are scattered throughout the quiz (you cannot answer the first question until you have read all ten).

• For starters, imagine the suspects. There are three men (George, John, Robert) and three women (Barbara, Christina, Yolanda). Each person is in a separate room (bathroom, dining room, kitchen, living room, pantry, office). A suspicious weapon was found in each room (bag, firearm, gas, knife, poison, rope). Question: who was found in the kitchen?
• Tip 1. When a man in the kitchen there is no rope, no knife, no bag. The weapon is not firearms. Question: what weapons are found in the kitchen?

• Tip 2. Barbara, either in the office or in the bathroom, and Yolanda - in another room of the two named. What room did you find Barbara in?
• Tip 3. The man with the bag is neither Barbara nor George, and he was neither in the bathroom nor in the dining room. Who had the bag?
• Tip 4. A woman with a rope is found in the office. Who is it?
• Tip 5. The weapon in the living room belongs to either John or George. What weapons in the living room?
• Tip 6. The knife was not in the dining room. Where was the knife?
• Tip 7. Yolanda was not in the office or in the pantry with the appropriate weapons for these rooms. What weapons have Yolanda?
• Tip 8. George found a firearm. In which room?
• It was discovered that Mr. Boddy was gassed in the pantry. The suspect in that room was the killer. Who is this?

I am dragged from such puzzles (actually almost from any puzzles). They could take hours and hours of thinking, but Prolog always comes to the rescue! Let's see how he helps to solve such problems on reasoning.

Prolog 101

SWI-Prolog installation

~> 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 - program-interpreter Prolog
• writeis called a functor, and a representation write/1means that it takes 1 argument (the same concept in Erlang and Elixir for adding the number of arguments to the function name)
• nl used to print a new line
• a sequence of commands is separated by commas, which also replace the AND operator
• the assignment operator is isfollowed by a mathematical expression
• variables are capitalized X, not x

Knowledge base

The essence of Prolog is in stating facts, compiling facts and inquiring them.

File creation 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).

• for loading we use [hello].: pay attention to the point at the end
• listing lists all the facts in the knowledge base

?- [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.

Request for Facts

After stating the facts in the knowledge base, we can go further and ask questions about the truth of the facts, as well as what conclusions can be drawn from them.

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

We can make more complex questions. For example, who is friends with John or who loves Julia.

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

John in a friendly zone?

We have established John-Julia ( friend(john, julia)) friendly relations , but for Prolog this does not mean that Julia is friends with John: we need to add one more fact friend(julia, john). Also, we have already indicated who has what children, and obviously do not want to duplicate the code, separately indicating the parents of each child. We don't want to write something like

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

Prolog helps to avoid duplication with the help of logical inference rules:

rule :- stmt1, stmt2,...

A rule is true if all internal statements are true (listed and logically folded comma-separated).

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

• the rule is friend(X,Y)valid when friend(Y,X)
• parent(X,Y) fair with the established child(Y,X)
• father(X,Y)fair with established parent(X,Y)andmale(X)
• mother(X,Y)fair with established parent(X,Y)andfemale(X)
• friendzoned(X)true if X loves SOMEONE Yand Y dislikes X (notice the hidden variable 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.

Well, now we have all the necessary knowledge. Let's practice on coloring the map.

Coloring card

Let's start with a well-known mathematical problem. It is required that no adjacent areas have the same color.



Therefore, the reasoning should be such, we have three things:

1. Variables are areas that we want to color: A, B, C, D, E.
2. Domain - the range of values ​​that can be assigned to variables: red, blue, green.
3. The restriction that adjacent areas cannot be the same color.

Domain

We define the domain of our regions (red, green, blue).

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

It's all.

Asking for a solution

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.

Here we define the solution as a rule colorifywith five variables A, B, C, D, E, and inside the rule we assign a domain color (red, blue, green) for variables and set restrictions that A is not equal to B, not equal to C ... and t dd

\+ X=Y means that X is not equal to Y

Prolog will continue to generate values ​​until it finds an option that satisfies the rule with restrictions.

?- [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.

... but we are not coloring the pictures here, but are looking for the killer.

Murder

For starters, imagine the suspects. There are three men (George, John, Robert) and three women (Barbara, Christina, Yolanda). Each person is in a separate room (bathroom, dining room, kitchen, living room, pantry, office). A suspicious weapon was found in each room (bag, firearm, gas, knife, poison, rope).

Who was found in the kitchen?

Domain

From this we can conclude that we have five domains: man, woman, personor suspect, locationand weapons, as our variables (A, B, C, D , E, F) must be present and a person and a place, and a weapon with certain restrictions, will be revealed in the upcoming tips.

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

The rule uniq_pplgenerates unique values ​​for our variables.

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.

Decision

We start by defining a killer rule with unique people in places and unique people with weapons, and now will indicate the relationship between people in places with those who have weapons.

Note that we still have six suspects.

Introduction

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

To easily talk about variables such as bathroom, canteen, firearms, gas, we immediately determine:

• Bathroom - is it a suspect (male or female) in the bathroom
• A firearm is the suspect (male or female) with a firearm
• and so on ... you can imagine it as a grid

Now we continue to add restrictions after the last comma in the rule murderer.

Tip 1

When a man in the kitchen there is no rope, knife or bag. The weapon is not firearms. What weapons found in the kitchen?

% 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,

Here we say that a variable Kitchensatisfies fact man(as defined in our domain), and declare that whoever the man in the kitchen, he has nothing of the following: Rope, Knife, Bag, Firearm.

Tip 2

Tip 2. Barbara, either in the office or in the bathroom, and Yolanda - in another room of the two named. What room did you find Barbara in?

Thus, we can say that womanthere is both in the office and in the bathroom. And this is not Christine, and we also delete other options for Barbara and Yolanda (kitchen, dining room, living room, pantry).

% % 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,

Tip 3

The man with the bag is neither Barbara nor George, and he was neither in the bathroom nor in the dining room. Who had the bag?

% % 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,

Tip 4

A woman with a rope was found in the office. Who is it?

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

Tip 5

Tip 5. The weapon in the living room belongs to either John or George. What weapons in the living room?

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,

Tip 6

The knife was not in the dining room. Where was the knife?

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

Tip 7

Tip 7. Yolanda was neither in the office nor in the pantry. What are the weapons in Yolanda's room?

% % 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,

Tip 8

George found a firearm.

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

Tip 9

It was discovered that Mr. Boddy was gassed in the pantry. The suspect in that room was the killer. Who is it?

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

Set the match for gas, pantry and killer, then use writeto display the answers 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.

Who is the killer?

 ?- [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 ;

The code is published here . It could probably be much better, since I am not an expert in the Prologue :)