The Fish Puzzle

Five houses stand in a row. Each is painted a different colour. Each is home to a person of a different nationality. Each person owns one distinct pet, smokes one distinct brand of cigar, and drinks one distinct beverage. A list of fifteen clues pins down every attribute of every house except one: the ownership of the fish. The solver is asked to determine who owns the fish.

The Fish puzzle, also known as Einstein’s Riddle and sometimes the Zebra Puzzle, is a classical exercise in constraint satisfaction. It has been attributed (without firm evidence) to Albert Einstein, to Lewis Carroll, and to a Life International puzzle compiler writing in December $1962$; the earliest published form is the $1962$ version, naming a zebra rather than a fish. The riddle is deceptively simple: the clues are short, the domain is only five houses, and yet the combinatorial structure is tight enough that the solution is unique.

Unlike the grid puzzles of Nikoli, Fish is a pure assignment puzzle: there is no spatial board, only a one-dimensional row of houses indexed $1$ through $5$, and five attribute categories each drawn from a size-$5$ alphabet. Each of the fifteen clues is a crisp logical predicate on one or two attribute values. The solver’s task is to find the single assignment of $25$ attribute values to $25$ attribute slots that satisfies every clue.

The CP-SAT encoding is exceptionally clean: each attribute value gets an integer variable in $\{0, 1, 2, 3, 4\}$ (representing the house index at which it sits), the five attribute categories each carry an $\operatorname{AllDifferent}$ constraint, and every clue reduces to either an equality, an order relation, or a Manhattan-$1$ adjacency constraint between two such variables.

Rules and a small instance

A Fish puzzle consists of $n$ houses in a row, each carrying $k$ attributes drawn from $k$ non-intersecting domains of size $n$ each (in the classical puzzle, $n = k = 5$). A solution assigns to each attribute value one of the $n$ house indices such that:

1. Within each attribute category, the $n$ values map to the $n$ house indices bijectively.

2. Every clue is satisfied.

In the classical instance the attribute categories are nationality, house colour, pet, cigar brand, and beverage. The fifteen clues are:

1. The Brit lives in the red house.

2. The Swede keeps dogs as pets.

3. The Dane drinks tea.

4. The green house is immediately to the left of the white house.

5. The green house owner drinks coffee.

6. The person who smokes Pall Mall rears birds.

7. The owner of the yellow house smokes Dunhill.

8. The person in the centre house drinks milk.

9. The Norwegian lives in the first house.

10. The Blends smoker lives next to the cat owner.

11. The horse owner lives next to the Dunhill smoker.

12. The Bluemaster smoker drinks beer.

13. The German smokes Prince.

14. The Norwegian lives next to the blue house.

15. The Blends smoker has a neighbour who drinks water.

The unique solution is shown in Figure 1.1.

	H1	H2	H3	H4	H5
Nationality	Norwegian	Dane	Brit	German	Swede
Colour	Yellow	Blue	Red	Green	White
Pet	Cat	Horse	Bird	Fish	Dog
Cigar	Dunhill	Blends	Pall Mall	Prince	Bluemaster
Beverage	Water	Tea	Milk	Coffee	Beer

The German owns the fish.

The programming model

The tightest encoding gives each attribute value the integer variable representing its house index. With $n = 5$ houses and $5$ categories of $5$ values each, the model has $25$ integer variables, each with domain $\{0, 1, 2, 3, 4\}$.

Domain bijection per category

For each attribute category $A$ (nationality, colour, pet, cigar, beverage), let $A_1, A_2, \ldots, A_5$ denote its five values as integer variables. Then $$\operatorname{AllDifferent}(A_1, A_2, A_3, A_4, A_5)$$ enforces that the five values occupy the five distinct houses.

Clue forms

The fifteen clues partition into three syntactic classes.

Identity clues. Most clues assert that two attribute values share a house. For example, clue $1$ (“the Brit lives in the red house”) becomes $$\mathrm{Nat}[\mathrm{Brit}] \;=\; \mathrm{Col}[\mathrm{Red}].$$ Clues $1, 2, 3, 5, 6, 7, 12, 13$ are of this form; so too are clues $8$ and $9$ (“centre house” and “first house” are specific indices, encoded as $\mathrm{Bev}[\mathrm{Milk}] = 2$ and $\mathrm{Nat}[\mathrm{Norwegian}] = 0$).

Order clue. Clue $4$ says the green house is immediately to the left of the white house. In the integer-variable encoding this is simply $$\mathrm{Col}[\mathrm{Green}] + 1 \;=\; \mathrm{Col}[\mathrm{White}].$$

Adjacency clues. Clues $10, 11, 14, 15$ are of the form “$X$ lives next to $Y$,” i.e. their house indices differ by exactly one. For clue $10$ (“the Blends smoker lives next to the cat owner”): $$\bigl| \mathrm{Cig}[\mathrm{Blends}] - \mathrm{Pet}[\mathrm{Cat}] \bigr| \;=\; 1,$$ encoded in CP-SAT via $\texttt{AddAbsEquality}$ on the difference.

A solver in forty lines

from ortools.sat.python import cp_model

NATS = ["Norwegian", "Dane", "Brit", "German", "Swede"]
COLS = ["Yellow", "Blue", "Red", "Green", "White"]
PETS = ["Cat", "Horse", "Bird", "Fish", "Dog"]
CIGS = ["Dunhill", "Blends", "Pallmall", "Prince",
        "Bluemaster"]
BEVS = ["Water", "Tea", "Milk", "Coffee", "Beer"]

def solve_fish():
    m = cp_model.CpModel()
    def attrs(names):
        return {n: m.NewIntVar(0, 4, n) for n in names}
    nat = attrs(NATS); col = attrs(COLS)
    pet = attrs(PETS); cig = attrs(CIGS); bev = attrs(BEVS)
    for d in (nat, col, pet, cig, bev):
        m.AddAllDifferent(list(d.values()))
    # Identity clues
    m.Add(nat["Brit"]   == col["Red"])        # 1
    m.Add(nat["Swede"]  == pet["Dog"])        # 2
    m.Add(nat["Dane"]   == bev["Tea"])        # 3
    m.Add(col["Green"]  + 1 == col["White"])  # 4
    m.Add(col["Green"]  == bev["Coffee"])     # 5
    m.Add(cig["Pallmall"] == pet["Bird"])     # 6
    m.Add(col["Yellow"] == cig["Dunhill"])    # 7
    m.Add(bev["Milk"]   == 2)                 # 8
    m.Add(nat["Norwegian"] == 0)              # 9
    m.Add(cig["Bluemaster"] == bev["Beer"])   # 12
    m.Add(nat["German"] == cig["Prince"])     # 13
    # Adjacency clues (|a - b| == 1)
    def adj(a, b):
        d = m.NewIntVar(-4, 4, "")
        ab = m.NewIntVar(0, 4, "")
        m.Add(d == a - b)
        m.AddAbsEquality(ab, d)
        m.Add(ab == 1)
    adj(cig["Blends"], pet["Cat"])            # 10
    adj(pet["Horse"],  cig["Dunhill"])        # 11
    adj(nat["Norwegian"], col["Blue"])        # 14
    adj(cig["Blends"], bev["Water"])          # 15
    s = cp_model.CpSolver()
    s.Solve(m)
    # Invert: house index -> attribute values
    out = [[""]*5 for _ in range(5)]
    for row, d in enumerate((nat, col, pet, cig, bev)):
        for name, var in d.items():
            out[row][s.Value(var)] = name
    return out

The puzzle solves uniquely in about $25$ milliseconds. Enumerating all feasible assignments (via $\texttt{parameters.enumerate\_all\_solutions} = \mathtt{True}$) confirms that precisely one assignment satisfies the fifteen clues.

Sources. The Fish puzzle first appeared in Life International in December $1962$ in its Zebra form (the unknown pet is a zebra; the magazine framed the puzzle as an attribution to Einstein, though no evidence supports this). The Fish variant circulates widely online and in logic-puzzle anthologies. The fifteen-clue formulation used here is the standard modern version; the uniqueness of solution hinges on the strict “immediately to the left” reading of clue $4$ (a relaxed “somewhere to the left” reading admits seven distinct assignments). The fixed $5 \times 5$ puzzle is a tiny finite search, decided at once. Its natural generalisation, in which $n$ houses carry $k$ attributes and the input is an arbitrary list of equality, order, and adjacency clues, is a constraint-satisfaction problem; deciding whether such a clue system is satisfiable is NP-complete in general, so for the unrestricted family no method essentially faster than search is to be expected.