The Logic Grid

Four friends, four pets, four drinks, four cities, and a handful of oblique clues: that is a logic grid puzzle. The kind filled magazine pages from the nineteen-eighties onward, the most famous being the one wrongly attributed to Einstein, and they are solved with a grid of ticks and crosses and no guesswork at all. Each clue rules something in or out, and the clues together leave exactly one consistent way to match everyone to everything. The solving is pure deduction, which is another way of saying it is a constraint-satisfaction problem, and the surprise is how few kinds of constraint the whole genre needs.

The puzzle

Ada, Bea, Cy and Dot each keep one pet, drink one drink and live in one city. The pets are a cat, a dog, a fish and a bird; the drinks are tea, cocoa, juice and water; the cities are Bath, Hull, Leeds and York. Every pet, drink and city belongs to exactly one friend. The clues are these.

1. Ada drinks tea.

2. The cat’s owner lives in York.

3. The fish’s owner drinks water.

4. Of Bea and Dot, one drinks juice and the other lives in Leeds.

5. The dog’s owner lives in Bath.

6. Ada does not keep the dog.

7. Dot drinks cocoa.

That is enough. The seven clues admit only one full matching, drawn in Figure 35.1, and a patient reader can reach it by elimination alone. We will reach it instead by writing the clues as linear constraints and letting a solver do the eliminating.

The model

The unknowns are three matchings, one between friends and pets, one between friends and drinks, one between friends and cities. Each is a grid of binary variables: $\mathrm{pet}_{i,v}$ is $1$ when friend $i$ keeps pet $v$, and $\mathrm{drink}_{i,v}$ and $\mathrm{city}_{i,v}$ likewise. A matching is a one-to-one pairing, so in each grid every friend takes exactly one value and every value goes to exactly one friend, $$\sum_{v} \mathrm{pet}_{i,v} = 1 \ \ (\text{each friend}), \qquad \sum_{i} \mathrm{pet}_{i,v} = 1 \ \ (\text{each pet}),$$ and the same two lines for drinks and for cities. These six families say only that the answer is a set of matchings; all the puzzle’s character lives in the clues.

Most clues are direct. “Ada drinks tea” fixes one variable to $1$; “Ada does not keep the dog” fixes one to $0$. The clue worth pausing on is the one that ties two grids together without naming a friend: “the cat’s owner lives in York.” It says nothing about who that owner is, only that whoever keeps the cat is whoever lives in York. Number the friends $1$ to $4$; then $\sum_i i\,\mathrm{pet}_{i,\,\mathrm{cat}}$ is the number of the cat’s owner and $\sum_i i\,\mathrm{city}_{i,\,\mathrm{York}}$ is the number of the York resident, and the clue is simply that the two numbers agree, $$\sum_i i\,\mathrm{pet}_{i,\,\mathrm{cat}} = \sum_i i\,\mathrm{city}_{i,\,\mathrm{York}} .$$ The same index-matching trick carries clues 3 and 5. Clue 4, an either-or about two named friends, is three small inequalities: exactly one of Bea and Dot drinks juice, exactly one lives in Leeds, and neither is both at once.

The solver

from ortools.sat.python import cp_model

PEOPLE = ["Ada", "Bea", "Cy", "Dot"]
PET = ["cat", "dog", "fish", "bird"]
DRINK = ["tea", "cocoa", "juice", "water"]
CITY = ["Bath", "Hull", "Leeds", "York"]
n = 4
ix = lambda lst, v: lst.index(v)

def solve_grid():
    m = cp_model.CpModel()
    pet = {(i, v): m.NewBoolVar("") for i in range(n) for v in range(n)}
    drk = {(i, v): m.NewBoolVar("") for i in range(n) for v in range(n)}
    cty = {(i, v): m.NewBoolVar("") for i in range(n) for v in range(n)}
    for g in (pet, drk, cty):              # each grid is a matching
        for i in range(n):
            m.Add(sum(g[i, v] for v in range(n)) == 1)
        for v in range(n):
            m.Add(sum(g[i, v] for i in range(n)) == 1)

    def same(g1, v1, g2, v2):              # the v1-holder is the v2-holder
        m.Add(sum(i * g1[i, v1] for i in range(n))
              == sum(i * g2[i, v2] for i in range(n)))

    A, B, D = 0, 1, 3
    m.Add(drk[A, ix(DRINK, "tea")] == 1)               # 1
    same(pet, ix(PET, "cat"), cty, ix(CITY, "York"))   # 2
    same(pet, ix(PET, "fish"), drk, ix(DRINK, "water"))  # 3
    ju, le = ix(DRINK, "juice"), ix(CITY, "Leeds")     # 4
    m.Add(drk[B, ju] + drk[D, ju] == 1)
    m.Add(cty[B, le] + cty[D, le] == 1)
    m.Add(drk[B, ju] + cty[B, le] <= 1)
    m.Add(drk[D, ju] + cty[D, le] <= 1)
    same(pet, ix(PET, "dog"), cty, ix(CITY, "Bath"))   # 5
    m.Add(pet[A, ix(PET, "dog")] == 0)                 # 6
    m.Add(drk[D, ix(DRINK, "cocoa")] == 1)             # 7

    s = cp_model.CpSolver()
    s.Solve(m)
    val = lambda g, i, lst: lst[next(v for v in range(n) if s.Value(g[i, v]))]
    return {PEOPLE[i]: (val(pet, i, PET), val(drk, i, DRINK), val(cty, i, CITY))
            for i in range(n)}

The program returns the matching of Figure 35.1: Ada with the cat and York, Bea with the dog and Bath, Cy with the fish and Hull, Dot with the bird and Leeds. It is the only matching the clues allow, a fact the solver will confirm if asked to find a second.

A grammar of clues

What makes the genre tractable is that almost every clue is one of a small number of shapes, and each shape has a fixed translation. “$A$ is $B$” sets a variable to one; “$A$ is not $B$” sets it to zero. “$A$ is either $B$ or $C$” sums two variables to one. The clue “the $B$ is the $C$,” linking two non-friend attributes, is the index-matching equation above, and “of $A$ and $B$, one is $C$ and the other $D$” is the little cluster of inequalities used for clue 4. A solver of these puzzles is really a translator: read each clue, recognise its shape, write its line, and hand the lot to a constraint solver that does the deduction the human would have done by hand, only without the ticks and crosses. A handful of templates covers a whole shelf of puzzle books.

What the puzzle teaches

The logic grid is the plainest possible face of constraint satisfaction: no objective, no optimisation, only a question of consistency, and a matching is either consistent with the clues or it is not. Two ideas earn their keep. The first is that a one-to-one matching is just an assignment grid with unit row and column sums, the same object behind timetabling and seating and a hundred other pairings. The second is the index-matching equation, which lets a clue speak about “the owner of the cat” without knowing who that is, by comparing the weighted position of a one in one grid with that in another. With those two pieces, a kind of puzzle that looks like a feat of verbal reasoning turns out to be a dozen lines of arithmetic, and the deduction the solver claims to need no luck for is the deduction a solver performs by construction.

Sources. The puzzle type and its integer-programming treatment, including the assignment constraints, the index-matching encoding of a clue that links two attributes, and the small grammar of clue-to-constraint translations, follow Martin J. Chlond, Puzzle—Logic Grid Puzzles, INFORMS Transactions on Education volume $15$, number $1$ ($2014$), pages $166$–$168$. The four-friend puzzle solved here is our own, with a unique solution confirmed by the model and a minimal set of clues, none removable without admitting a second answer. The genre’s most celebrated specimen, the so-called Einstein or zebra puzzle, is modelled by Julian Scott Yeomans, Solving Einstein’s Riddle Using Spreadsheet Optimization, INFORMS Transactions on Education volume $3$, number $2$ ($2004$), pages $55$–$63$.