Previous articles in this series:
This is a classic Prolog exercise. The Chinese translation is from Ruan Yifeng's article Introduction to Prolog language.
problem
Mr. Boddy died of murder. There are six suspects. Each of them is in a different room. Each room has a possible murder weapon, but he does not know the corresponding relationship among the suspect, the room and the murder weapon. Please find out who the killer is according to the following conditions and clues.
The six suspects are three men (George, John, Robert) and three women (Barbara, Christine, Yolanda).
The six suspects were in six rooms: Bathroom, Dining Room, Kitchen, Living Room, Pantry and Study. Each room has a suspicious object that can be used as a weapon: Bag, Firearm, Gas, Knife, Poison, Rope.
All clues are as follows:
Clue 1: there is a man in the kitchen. The murder weapon there is not rope, knife, bag and musket.
Clue 2: Barbara and Yolanda are in the bathroom and study.
Clue 3: the man with the bag is not Barbara and George, nor is he in the bathroom or dining room.
Clue 4: there is a woman with a rope in the study.
Clue 5: the murder weapon in the living room, with John or George.
Clue 6: the knife is not in the dining room.
Clue 7: the murder weapon in the study and pantry, not with Yolanda.
Clue 8: George's room has a musket.
Clue 9: Mr. Boddy died in the pantry, where the murder weapon was gas.
Nmini kanren solving problems
Direct code:
var George = "George";
var John = "John";
var Rebert = "Rebert";
var Barbara = "Barbara";
var Christine = "Christine";
var Yolanda = "Yolanda";
var res = KRunner.Run(10, (k, q) =>
{
// Men gather
var manNames = new string[] { George, John, Rebert };
var man = k.List(manNames);
// Women gather
var womanNames = new string[] { Barbara, Christine, Yolanda };
var woman = k.List(womanNames);
// All together
var person = k.List(manNames.Concat(womanNames).ToArray());
// People in each place
var bathroom = k.Fresh();
var dining = k.Fresh();
var kitchen = k.Fresh();
var livingroom = k.Fresh();
var pantry = k.Fresh();
var study = k.Fresh();
// Article holder
var bag = k.Fresh();
var firearm = k.Fresh();
var gas = k.Fresh();
var knife = k.Fresh();
var poison = k.Fresh();
var rope = k.Fresh();
// Different people in different rooms
var locationConst = k.Distincto(bathroom, dining, kitchen, livingroom, pantry, study);
// Different people hold different things
var weaponConst = k.Distincto(bag, firearm, gas, knife, poison, rope);
// The variable X represents the killer
var X = k.Fresh();
// clue
// There was a man in the kitchen. The weapons were not ropes, knives, bags and muskets.
var clue1 = k.All(
k.Is(kitchen, man),
k.Noto(k.Eq(kitchen, rope), k.Eq(kitchen, knife), k.Eq(kitchen, bag), k.Eq(kitchen, firearm)));
// Barbara and Yolanda are in the bathroom and study.
var clue2 = k.Any(
k.All(k.Eq(bathroom, Barbara), k.Eq(study, Yolanda)),
k.All(k.Eq(bathroom, Yolanda), k.Eq(study, Barbara)));
// The man with the bag is not Barbara and George, nor is he in the bathroom or dining room.
var clue3 = k.Noto(
k.Eq(bag, Barbara), k.Eq(bag, George),
k.Eq(bag, bathroom), k.Eq(bag, dining));
// In the study is a woman with a rope.
var clue4 = k.All(k.Is(rope, woman), k.Eq(rope, study));
// The murder weapon in the living room, with John or George.
var clue5 = k.Any(k.Eq(livingroom, John), k.Eq(livingroom, George));
// The knife is not in the dining room.
var clue6 = k.Noto(k.Eq(knife, dining));
// The murder weapon in the study and the pantry, not with Yolanda.
var clue7 = k.Noto(k.Eq(study, Yolanda), k.Eq(pantry, Yolanda));
// George's room has guns.
var clue8 = k.Eq(firearm, George);
// Mr. Boddy died in the pantry, where the murder weapon was gas.
var clue9 = k.All(k.Eq(X, pantry), k.Eq(X, gas));
// Set all conditions
return k.All(
k.Is(X, person),
k.Is(bathroom, person),
k.Is(dining, person),
k.Is(kitchen, person),
clue5,
k.Is(livingroom, person),
k.Is(pantry, person),
k.Is(study, person),
clue2,
locationConst,
k.Is(bag, person),
k.Is(firearm, person),
clue8,
k.Is(gas, person),
k.Is(knife, person),
k.Is(poison, person),
k.Is(rope, person),
weaponConst,
clue1,
clue3,
clue4,
clue6,
clue7,
clue9,
k.Eq(q, k.List(
bathroom, dining, kitchen, livingroom, pantry, study,
bag, firearm, gas, knife, poison, rope,
X)));
});
Console.WriteLine("(bathroom dining kitchen livingroom pantry study bag firearm gas knife poison rope X)");
KRunner.PrintResult(res);
Some of them are auxiliary functions
k.Is(a, s): a is a member of the set s.
k.Noto(g1, g2, ...): g1,g2…… Neither. NMiniKanren does not support the "not" operation, which is simulated by If method, only in some cases.
k.Distincto(a, b, c, ...): a,b,c…… The two are not equal.
Complete code in https://github.com/sKabYY/NMiniKanren/blob/master/NMiniKaren.Tests/Crime.cs
In addition, the final use of k.All to integrate all conditions is not written in order. After understanding the operating principle of nmini kanren, you will know that this is because the different sequence will affect the running speed. In general, try to put as few branches as possible in front.
Click Run, wait for dozens of seconds, output the result:
(bathroom dining kitchen livingroom pantry study bag firearm gas knife poison rope X) [(Yolanda George Rebert John Christine Barbara John George Christine Yolanda Rebert Barbara Christine)]
The killer is Christine.