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 - Prolog interpreter program
• write is called a functor, and the write/1 representation means 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 followed by a mathematical expression
• variables are written in uppercase X , not x

Knowledge base

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

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

• to download use [hello]. : notice the point at the end
• listing lists all 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 a friendly relationship with John and Julia ( friend(john, julia) ), but for Prolog this does not mean that Julia is friends with John: you need to add another friend(julia, john) 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). 

• friend(X,Y) rule holds for friend(Y,X )
• parent(X,Y) holds for child(Y,X)
• father(X,Y) true when parent(X,Y) and male(X)
• mother(X,Y) true when parent(X,Y) and female(X)
• friendzoned(X) valid if X loves SOMEONE Y , and Y dislikes X (noticed 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 a solution as a rule colorify with 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 etc.

\+ 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 , person or suspect, location and weapons , and our variables (A, B, C, D, E, F) should represent the person, the place, and the weapon with some limitations that 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 uniq_ppl rule generates 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 begin 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.

Please 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 murderer rule.

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 the variable Kitchen satisfies the fact man (defined in our domain), and declare that whoever the person in the kitchen is, 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 a woman is in the office and in the bathroom. And this is not Christina, 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 a match for gas, pantry, and killer, then use write to print writeanswers responses.

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