# Copyright (C) 2004 Lauri Karttunen

#

# This program is free software; you can redistribute it and/or
modify

# it under the terms of GNU
General Public License
as published by

# the Free Software Foundation; either version 2 of the License, or

# (at your option) any later
version.

# This program is distributed in the hope that it will be
useful,

# but WITHOUT ANY WARRANTY; without even the implied
warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the

# GNU General Public License for more details.

Let us assume that there are five houses of different colors next to each other on the same road. In each house lives a man of a different nationality. Every man has his favorite drink, his favorite brand of cigarettes, and keeps pets of a particular kind.

- The Englishman lives in the red house.
- The Swede keeps dogs.
- The Dane drinks tea.
- The green house is just to the left of the white one.
- The owner of the green house drinks coffee.
- The Pall Mall smoker keeps birds.
- The owner of the yellow house smokes Dunhills.
- The man in the center house drinks milk.
- The Norwegian lives in the first house.
- The Blend smoker has a neighbor who keeps cats.
- The man who smokes Blue Masters drinks bier.
- The man who keeps horses lives next to the Dunhill smoker.
- The German smokes Prince.
- The Norwegian lives next to the blue house.
- The Blend smoker has a neighbor who drinks water.

The question to be answered is: **Who keeps fish?**

define Color [blue | green | red | white | yellow];

define Nationality [Dane | Englishman | German | Swede | Norwegian];

style="font-weight: bold;"> define Drink [bier | coffee | milk |tea | water];

define Cigarette [Blend | BlueMaster | Dunhill | PallMall | Prince];

define Pet [birds | cats | dogs | fish | horses];

The next concept to define is that of a `House`. Let us
construe it as a concatenation of the five terms defined above:

defineHouse[Color Nationality Drink Cigarette Pet];

With five variables each taking one of five possible values, this
gives quite a number of possible households, 5x5x5x5x5 = 3125, to be
exact. A road with five houses next to each other, `House^5`,
provides an astronomical number of possible combinations of colors,
nationalities, drinks, cigarettes and pets.

To solve Einstein's puzzle, we represent each of the fifteen
constraints as a regular language and intersect these languages with
the initial set of all possibilities. If all goes well, at the end we
will know who keeps fish. For example, we can interpret *The
Englishman lives in the red house.* as `$[red Englishman]`.
This constraint is trivial to encode because in our representation of a
house, the color and the nationality are adjacent. The second
costraint, *The Swede keeps dogs* could be represented as `$[Swede
Drink Cigarette dogs]` but we will choose a less verbose
formulation, `$[Swede ~$Pet dogs]`,
that does not explicitly
list the variables that separate `Nationality` and `Pet`.
The fifteen constraints are shown below.

defineC1$[red Englishman];

#The Englishman lives in the red house.defineC2$[Swede ~$Pet dogs];

#The Swede keeps dogs.defineC3$[Dane tea];

#The Dane drinks tea.defineC4$[green ~$Color white];

#The green house is just to the left of the white one.defineC5$[green ~$Drink coffee];

#The owner of the green house drinks coffee.defineC6$[PallMall birds];

#The Pall Mall smoker keeps birds.defineC7$[yellow ~$Cigarette Dunhill];

#The owner of the yellow house smokes Dunhills.defineC8[House^2 ~$Drink milk ~$Drink House^2];

#The man in the center house drinks milk.defineC9[? Norwegian ?*];

#The Norwegian lives in the first house.defineC10$[Blend ? ~$Pet cats | cats ~$Cigarette Blend];

#The Blend smoker has a neighbor who keeps cats.defineC11$[horses ~$Cigarette Dunhill | Dunhill ? ~$Pet horses];

#The man who keeps horses lives next to the Dunhill smoker.defineC12$[bier BlueMaster];

#The man who smokes Blue Masters drinks bier.defineC13$[German ~$Cigarette Prince];

#The German smokes Prince.defineC14$[Norwegian ~$Color blue | blue ? ~$Nationality Norwegian];

#The Norwegian lives next to the blue house.defineC15$[Blend ~$Drink water | water ? ~$Cigarette Blend];

#The Blend smoker has a neighbor who drinks water.

All that we need to do to solve the problem is to impose the constraints on the row of five houses by intersection. The solution below is almost correct.

defineSolution [House^5 & C1 & C2 & C3 &C4 & C5 &

C6 & C7 & C8 & C9 & C10 &

C11 & C12 & C13 & C14 & C15];

The result is a network with five paths. In four of the solutions nobody keeps fish and the German keeps the same kind of pet as someone else. We need one final constraint, presupposed by the question Who keeps fish?:

defineC16$fish;

#There is someone who keeps fish.

With `C16` added, only one
solution remains. To make it
easier to see, we compose the solution with the transducer that adds
some prose around the pieces along the one remaining path:

defineDescribe[House -> "In the " ... .o.

Color -> ... " house " .o.

Nationality -> "the " ... " " .o.

Drink -> "drinks "... ", " .o.

Cigarette -> "smokes "... "s,\n and " .o.

Pet -> "keeps " ... ".\n"] ;

We can now see the solution.

regex [Solution .o. Describe];

76 states, 75 arcs, 1 path.

xfst[2]: print lower-words

In the yellow house the Norwegian drinks water, smokes Dunhills,

and keeps cats.

In the blue house the Dane drinks tea, smokes Blends,

and keeps horses.

In the red house the Englishman drinks milk, smokes PallMalls,

and keeps birds.

In the green house the German drinks coffee, smokes Princes,

and keeps fish.

In the white house the Swede drinks bier, smokes BlueMasters,

and keeps dogs.

**In short, it's the German who keeps fish.**

But are we sure that this is the only right solution? The conception of a row
of houses, `House^5`, assumes that the five houses are located side by side
along a road. No houses are facing each other from the opposite sides of the road.
What is left unspecified is the orientation of the observer. Assuming that the houses
are all on the same side of the road, are we on the side of the houses facing the road
or on the opposite side facing the row of houses? The interpretation of left and right
depends on the orientation of the observer.

As Daniel White (a student at UPenn) pointed out to me, the encoding of C4

define C4 $[green ~$Color white];

# The green house is just to the left of the white one.

assumes that we are looking at the houses from the other side of the road. What if we flip our orientation? In that case, the encoding of C4 should be

But what if we are undecided about the orientation, allowing either one of the two possibilities? In that case C4 should be formulated as a disjunction like C10, C14 and C15:define C4 $[white ~$Color green];

# The green house is just to the left of the white one.

define C4 $[green ~$Color white] | $[white ~$Color green];

# The green house is just to the left of the white one.

Try the alternative formulations of C4 and see if they make a difference for the solution for the
puzzle: *Who keeps fish?"*

Another option is to give up the idea of a fixed orientation. Let it be replaced
by the orientation of an observer moving along the road with houses on both sides of the road. Assuming
that the road runs North-South and the observer is traveling northward, *left* means ‘west’ and
*right* means ‘east,’ the opposite if the observer is traveling southward. Would that scenario
produce a different outcome for C4?