The Riddle of the Pilgrims

In The Canterbury Puzzles ($1907$), H. E. Dudeney poses a bedroom-allocation problem styled after Chaucer’s pilgrims: a company must be lodged in a two-storey dormitory, subject to a short list of the Abbot’s constraints. Each floor is a $3 \times 3$ array of rooms with a central staircase, leaving eight rooms per floor and sixteen total. The Abbot’s rules are:

1. every room holds between one and three pilgrims, inclusive;

2. each of the four sides of the building lodges exactly eleven pilgrims (the three rooms on that side of the lower floor together with the three rooms on that side of the upper floor);

3. the upper floor holds exactly twice as many pilgrims as the lower floor.

When the pilgrims arrive, the group turns out to number three more than was first announced, and the monks must produce a second allocation — satisfying the same three rules — for the larger party. The puzzle’s entire force lies in showing that the first total and the second total are uniquely determined. The answer is that the first allocation lodges $27$ pilgrims and the second $30$.

The programming model

The problem is a small integer-programming feasibility instance with fewer than twenty variables and a handful of linear equalities.

Variables

Index rooms by $(f, r, c)$ with $f \in \{0, 1\}$ the floor (lower, upper) and $(r, c) \in \{0, 1, 2\}^2$ the cell. Let $x_{f, r, c} \in \{1, 2, 3\}$ be the number of pilgrims in the room at $(f, r, c)$; the staircase cells $(f, 1, 1)$ are excluded by setting $x_{f, 1, 1} = 0$.

Side totals

For each of the four sides, the sum over the six rooms on that side (three cells on the lower floor, three on the upper) equals $11$. Writing $s_R$ for rows $r \in \{0, 2\}$ and $s_C$ for columns $c \in \{0, 2\}$: $$\sum_{f \in \{0, 1\}} \sum_{c = 0}^{2} x_{f, s_R, c} \;=\; 11, \quad \sum_{f \in \{0, 1\}} \sum_{r = 0}^{2} x_{f, r, s_C} \;=\; 11.$$

Upper-lower ratio

$$\sum_{r, c} x_{1, r, c} \;=\; 2 \sum_{r, c} x_{0, r, c}.$$

Total feasibility

Let $T = \sum_{f, r, c} x_{f, r, c}$. The problem does not fix $T$: we want to know which values of $T$ admit a valid allocation. The CP-SAT model with parameters.enumerate_all_solutions = True reveals exactly two: $T = 27$ and $T = 30$. These are the first and second allocations.

A solver in twenty lines

from ortools.sat.python import cp_model

def solve(total=None):
    m = cp_model.CpModel()
    x = {}
    for f in range(2):
        for r in range(3):
            for c in range(3):
                if (r, c) == (1, 1):
                    x[(f, r, c)] = m.NewIntVar(0, 0, "")
                else:
                    x[(f, r, c)] = m.NewIntVar(1, 3, "")
    for r in (0, 2):
        m.Add(sum(x[(f, r, c)]
                  for f in range(2)
                  for c in range(3)) == 11)
    for c in (0, 2):
        m.Add(sum(x[(f, r, c)]
                  for f in range(2)
                  for r in range(3)) == 11)
    lower = sum(x[(0, r, c)]
                for r in range(3)
                for c in range(3))
    upper = sum(x[(1, r, c)]
                for r in range(3)
                for c in range(3))
    m.Add(upper == 2 * lower)
    if total is not None:
        m.Add(lower + upper == total)
    s = cp_model.CpSolver()
    s.Solve(m)
    return {k: s.Value(v) for k, v in x.items()}

The two allocations

Figure 15.1 displays a representative first allocation ($27$ pilgrims) and Figure 15.2 the unique-in-total second allocation ($30$ pilgrims). In each figure, the lower floor is on the left and the upper floor on the right; the staircase is the shaded central cell; the number in each other cell is the pilgrim count; row and column sums are annotated.

The existence of exactly two feasible totals ($27$ and $30$) is the fact that resolves Dudeney’s riddle: the monks’ increase of three pilgrims must bring the lodgers from $27$ up to $30$, because no intermediate total is possible under the rules.

Sources. Dudeney’s The Canterbury Puzzles ($1907$) gathers puzzles framed around Chaucerian pilgrims; the riddle here appears in the chapter “The Merry Monks of Riddlewell” as Problem 25. The puzzle’s statement is elementary but its mechanics — the constraint structure determining a finite set of admissible totals, with the step of three pilgrims landing on exactly the next admissible value — anticipate the formal study of integer-programming feasibility by several decades. The CP-SAT enumeration offered above is in principle overkill for a problem with sixteen variables, but it demonstrates, in a single call, that the reasoning underlying Dudeney’s solution has no hidden case left to check.