The Task
The Zebra puzzle, a.k.a. Einstein's Riddle, is a logic puzzle which is to be solved programmatically.
It has several variants, one of them this:
- There are five houses
- The English man lives in the red house.
- The Swede has a dog.
- The Dane drinks tea.
- The green house is immediately to the left of the white house.
- They drink coffee in the green house.
- The man who smokes Pall Mall has birds.
- In the yellow house they smoke Dunhill.
- In the middle house they drink milk.
- The Norwegian lives in the first house.
- The man who smokes Blend lives in the house next to the house with cats.
- In a house next to the house where they have a horse, they smoke Dunhill.
- The man who smokes Blue Master drinks beer.
- The German smokes Prince.
- The Norwegian lives next to the blue house.
- They drink water in a house next to the house where they smoke Blend.
Who owns the Zebra?
Additionaly, we should mention that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarets.
How to solve it
This kind of task is quite hard to solve manually. It's not really complex, but rather complicated because there are so many options to consider.
However, it is really well suited to be solved with help of logical programming. The concept of logical programming is to write down all known information into a knowledge base and run queries on it.
So you might already have guessed that our chosen tool for this one will be Pilog.
Defining the main predicate match
Apparently, we are having five persons, each of them can be recognized by five distinctive attributes: house color, nationality, drink, pet and cigarette. Let's see what we can make out of it.
These five people are living in five houses in a row. We can map this to a list where the first item corresponds to the house on the outer left, and the last item to the house on the outer right:
( Person1 Person2 Person3 Person4 Person5)
If we could find the attributes of each of these persons, the riddle is solved. This can be written down as a list of lists. Let's define a predicate match that should contain our final solution:
(be match (@House @Person @Drink @Pet @Cigarettes)
...)
This is the left side of our predicate. Now we need to define the right side: All the conditions that need to be fulfilled.
The permute predicate
We know all the attributes, but unfortunately we don't have all information about the correct order. For example, if we read the text carefully, we notice that there must be a yellow, blue, red, green and white house. There are 5! = 120 possibilities to arrange these five colors into lists.
However, Pilog offers a handy function to do it for us: The permute predicate. We can use it in two ways:
Querying it for all possible permutations of a list:
: (? (permute (a b c) @L))
@L=(a b c)
@L=(a c b)
@L=(b a c)
@L=(b c a)
@L=(c a b)
@L=(c b a)
-> NIL
Checking if a combination is a permutation of the original list:
: (? (permute (a b c) (c b a)))
-> T
: (? (permute (a b c) (c b d)))
-> NIL
So, although we don't know the order yet, at least we know that the following condition must be fulfilled: The final list @House must be a permutation of the five color elements:
(permute (red blue green yellow white) @House)
Similarly, we can define @Nationality, @Drink, @Dog and @Cigarettes. This is what we have so far:
(be match (@House @Nationality @Drink @Pet @Cigarettes)
(permute (red blue green yellow white) @House)
(permute (Norwegian English Swede German Dane) @Nationality)
(permute (tea coffee milk beer water) @Drink)
(permute (dog birds cats horse zebra) @Pet)
(permute (Pall-Mall Dunhill Blend Blue-Master Prince) @Cigarettes) )
Defining positions
We have the following straightforward information:
- In the middle house they drink milk.
- The Norwegian lives in the first house.
So we know that the @Nationality list starts with Norwegian, and the third element of the @Drink list is milk.
We can check equality with the equal predicate: "Is the list starting with Norwegian equal to our list @Person? Since we have no further information about the rest, we use the @ symbol. So we add this to match:
(equal @Nationality (Norwegian . @))
(equal @Drink (@ @ milk . @))
Connecting two attributes
If we go back to the task lists, we find many descriptions such as: "Person X has/drinks/smokes Y". For example:
- The English man lives in the red house.
- The Swede has a dog.
- The Dane drinks tea.
We said that each of our @House, @Drink lists describe "left house to right house". So, if "English" is in position p in the @Nationality list, then red must be in the same position in the @House list.
Let's write that down in Pilog. Like described in the "More Lists"-post of the Pilog course, we need a recursive definition. The base case is the head of the list. We call the predicate has (from "the Person has ..."):
(be has ((@A . @X) @A (@B . @Y) @B))
"If @A is the head of list @X, then @B is the head of list @Y".
If it happens to be not the head, we travel down recursively by taking only the tail of the list:
(be has ((@ . @X) @A (@ . @Y) @B)
(has @X @A @Y @B) )
Now we can translate the statements from above to Pilog. In total, there are 8 conditions of this type: 2, 3, 4, 6, 7, 8, 13 and 14.
(has @Nationality English @House red)
(has @Pet dog @Person Swede)
(has @Drink tea @Person Dane)
(has @Drink coffee @House green)
(has @Cigarettes Pall-Mall @Pet birds)
(has @Cigarettes Dunhill @House yellow)
(has @Cigarettes Blue-Master @Drink beer)
(has @Cigarettes Prince @Person German)
Defining the right-of / left-of / next-to condition
In the text, we find many conditions similar to: "Person X is next to Person Y", where "Person" is replaced by one of its attributes:
- The green house is immediately to the left of the white house.
- The man who smokes Blend lives in the house next to the house with cats.
How can we describe @A is left of @B? It means that if @A is the first in our list, than @B must be second in our list. Again, we define recursively, first the base case:
(be right-of ((@A . @X) @A (@ @B . @Y) @B))
(be left-of ((@ @A . @X) @A (@B . @Y) @B))
Now the recursive part.
(be right-of ((@ . @X) @A (@ . @Y) @B)
(right-of @X @A @Y @B) )
(be left-of ((@ . @X) @A (@ . @Y) @B)
(left-of @X @A @Y @B) )
Logic is the same as before: If our condition is false for the head, than we repeat recursively with the first item of the tail.
next-to is a little bit less specific: It could both be left or right.
(be next-to (@X @A @Y @B) (right-of @X @A @Y @B))
(be next-to (@X @A @Y @B) (left-of @X @A @Y @B))
Now we can add these to our conditions list:
(left-of @House white @House green)
(next-to @Cigarettes Blend @Pet cats)
(next-to @Cigarettes Dunhill @Pet horse)
(next-to @Nationality Norwegian @House blue)
(next-to @Drink water @Cigarettes Blend) )
and it fails...?!
With this, we have covered all conditions from the task description! Let's start the script and check it.
$ pil zebra.l +
: (?(@House @Nationality @Drink @Pet @Cigarettes)
Unfortunately, we don't get a result. It's also not crashing. It just seems to take a veery long time to compute - I don't know how long because I cancelled it.
In order to understand this, we need to go back to think about how pilog actually works. Keyword: Backtracking.
The Order matters!
Pilog takes each condition of our match prediacte and checks it. If a solution fails, it goes back and checks the next permutation. However, we started with the permutations:
(be match (@House @Person @Drink @Pet @Cigarettes)
(permute (red blue green yellow white) @House)
(permute (Norwegian English Swede German Dane) @Person)
(permute (tea coffee milk beer water) @Drink)
(permute (Pall-Mall Dunhill Blend Blue-Master Prince) @Cigarettes)
(permute (dog birds cats horse zebra) @Pet)
These first five lines have 120 possible permutation each and there is no condition which excludes any of these. This is a very bad design: We should have tried to narrow down each of these permutations to an earliest stage as possible in order to avoid unnecessary backtracking.
Now that we understood this, let's re-order the information we have.
First we write down all information we have about the @House list, then about the @Nationality list, and so on. The advantage is that if we hit a NIL evaluation, we can go back and test a different permutation..
(be match (@House @Nationality @Drink @Pet @Cigarettes)
(permute (red blue green yellow white) @House)
(left-of @House white @House green)
(permute (Norwegian English Swede German Dane) @Nationality)
(has @Nationality English @House red)
(equal @Nationality (Norwegian . @))
(next-to @Nationality Norwegian @House blue)
...
After restructuring the match predicate, Pilog finds the answer almost immediately. There is only one:
: (? ( match @House @Nationality @Drink @Pet @Cigarettes))
@House=(yellow blue red green white) @Nationality=(Norwegian Dane English German Swede) @Drink=(water tea milk coffee beer) @Pet=(cats horse birds zebra dog) @Cigarettes=(Dunhill Blend Pall-Mall Prince Blue-Master)
Printing it nicely
Our output is correct but not very readable, and we have to repeat the query each time we start the script.
So let's do it differently: With the (PicoLisp) function (pilog 'lst . prg) we can evaluate a Pilog query and execute prg for the result set. Like this:
(pilog '((match @House @Person @Drink @Pet @Cigarettes))
... )
Now we can use PicoLisp functions to work with the lists.
With the tab function, we can print the output in a tab format. It takes a list of numbers as argument which specify the individual field widths. If the number is negative, all items are left-aligned, otherwise right-aligned.
(let Fmt (-12 -12 -12 -12 -12)
(tab Fmt "HOUSE" "NATION" "DRINKS" "PET" "CIGARETTE")
Then we evaluate all items per list in the same way with mapc. mapc takes a functiona nd a list, and applies the function to each element. The function we want to pass to it is (tab Fmt). First we need to pass Fmt to tab using the pass function. The result of this evaluation (@) will be passed to mapc.
(mapc '(@ (pass tab Fmt))
@House @Person @Drink @Pet @Cigarettes ) ) )
When we now start the script with pil zebra.l, we get this output:
$ pil zebraRiddle.l
HOUSE PERSON DRINKS HAS SMOKES
yellow Norwegian water cats Dunhill
blue Dane tea horse Blend
red English milk birds Pall-Mall
green German coffee zebra Prince
white Swede beer dog Blue-Master
The final script can be found here.
Sources
https://en.wikipedia.org/wiki/Zebra_Puzzle
https://rosettacode.org/wiki/Zebra_puzzle#PicoLisp
