The Dogs of the Round Table

King Arthur granted a few of his dogs the honour of a place at the Round Table. How many were so favoured is not stated outright. Instead Raymond Smullyan, who tells the tale, scatters the count through a list of tallies. Each dog is male or female, shaggy or not, large or small, and we are told only this: there are twelve males, fourteen shaggy dogs and thirteen large ones; four are large and shaggy, three are large males, five are shaggy males; exactly one is a large shaggy male, and no female is at once small and non-shaggy. From that the whole census can be recovered, and with it the number at the table.

Eight cells, eight facts

The three attributes cut the dogs into $2 \times 2 \times 2 = 8$ kinds. Write $x_{ijk}$ for the number of dogs of gender $i$, shagginess $j$ and size $k$, each index running over its two values, and the puzzle is to fill this little three-dimensional array of eight counts.

Every clue is a sum over a slice of the array. “Twelve males” fixes the total over the four cells with $i$ male; “four large shaggy” fixes the sum over the two cells that are large and shaggy, of either gender; and the two sharpest clues name single cells, the lone large shaggy male and the absent small non-shaggy female. Six clues are slice sums and two are single cells, eight facts for eight unknowns.

from ortools.sat.python import cp_model
from itertools import product

def solve():
    m = cp_model.CpModel()
    cells = list(product(range(2), repeat=3))  # (gender, shag, size)
    x = {c: m.NewIntVar(0, 100, "") for c in cells}

    def tally(g=None, sh=None, sz=None):       # sum over a slice
        return sum(x[i, j, k] for i, j, k in cells
                   if (g is None or i == g)
                   and (sh is None or j == sh)
                   and (sz is None or k == sz))

    m.Add(tally(g=0) == 12)            # twelve males
    m.Add(tally(sh=0) == 14)           # fourteen shaggy
    m.Add(tally(sz=0) == 13)           # thirteen large
    m.Add(tally(sh=0, sz=0) == 4)      # four large and shaggy
    m.Add(tally(g=0, sz=0) == 3)       # three large males
    m.Add(tally(g=0, sh=0) == 5)       # five shaggy males
    m.Add(x[0, 0, 0] == 1)             # one large shaggy male
    m.Add(x[1, 1, 1] == 0)             # no small non-shaggy female
    s = cp_model.CpSolver()
    s.Solve(m)
    table = {c: s.Value(x[c]) for c in cells}
    return table, sum(table.values())

Why it comes out exactly

The program returns twenty-eight dogs, in the arrangement of Figure 39.1. Smullyan’s clues are not merely sufficient, they are exactly so, and one can watch them resolve the array a cell at a time. The lone large shaggy male is given. The five shaggy males then leave four small shaggy males; the three large males leave two large non-shaggy males; the twelve males leave five small non-shaggy males. The four large shaggy dogs leave three large shaggy females, the fourteen shaggy dogs leave six small shaggy females, the thirteen large dogs leave seven large non-shaggy females, and the last clue empties the final cell. The eight facts form a triangular system: ordered rightly, each peels off one new count, which is why pencil-and-paper back-substitution solves the puzzle and why an optimiser is not needed to find the answer.

What the model is good for is the question behind the puzzle: is the count truly forced? It is. Asking the solver for the largest and the smallest total consistent with the eight clues returns twenty-eight both ways, so no cell has any freedom. And every clue earns its place: drop any one and the total is no longer determined. Removing a population tally, the twelve males say, lets that category grow without bound; removing a cross-tally such as the three large males leaves a smaller but still genuine range. Reconstructing a table of counts from sums over its slices is in general an underdetermined problem, the kind that linear and integer programming are built to probe, and this puzzle is the rare instance where the slices pin every cell.

Sources. The “Dogs of the Round Table” puzzle is from Raymond M. Smullyan, King Arthur in Search of His Dog and Other Curious Puzzles (Dover, New York, $2010$). The presentation as a three-dimensional array of counts with each clue a sum over a slice, and the integer-programming treatment, follow Martin J. Chlond, Integer Programming in King Arthur’s Court, INFORMS Transactions on Education volume $13$, number $3$ ($2013$), pages $172$–$173$. The total of twenty-eight, the uniqueness of the census, and the fact that all eight clues are necessary are reproduced by the model above and re-derived independently: the solver confirms that the largest and smallest totals consistent with the clues are both twenty-eight, and that dropping any single clue makes the total no longer unique.