Fantasy OR

The Sangraal is almost won. You reach the castle where the Foul Fiend has imprisoned eight knights, and the sun sets in twenty minutes. Each knight must be untied and then sent off to wash and compose himself before the Grail arrives; only those ready in time may come. You can untie one knight at a time, but they wash in parallel once freed. Whom do you save, and how many?

One rescuer, eight knights

The eight are Agravain through Harry. Untying takes a single rescuer, so it happens in sequence: the knights are freed one after another, and the order is yours to choose. The times to free them, in minutes, run $1, 1, 2, 2, 3, 4, 5, 6$. Washing is the opposite: a freed knight walks off and prepares on his own, in parallel with the next untying, taking $5$, $10$ or $15$ minutes by how badly he is hurt. Here are the two figures per knight, free time $f_i$ above, prep time $r_i$ below: $$\begin{array}{c|cccccccc} & A & B & C & D & E & F & G & H \\ \hline f_i & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 6 \\ r_i & 15 & 5 & 15 & 5 & 10 & 15 & 10 & 5 \end{array}$$ A knight is ready when he has been freed and has finished washing. If you free knights in some order, the one untied $j$th is freed only once the rescuer has worked through all $j$ knights before and including him, so his freeing finishes at the running total of those free times; then he washes. His ready time is therefore the cumulative free time through his turn, plus his own prep.

Were the aim to free and ready everyone as fast as possible, this would be an ordinary one-machine scheduling problem. The twist is that we cannot ready everyone in twenty minutes, so we maximise the number made ready in time.

The model

Let $x_{ij} = 1$ if knight $i$ is freed $j$th. Each knight takes one slot and each slot one knight: $$\sum_j x_{ij} = 1 \quad \forall i, \qquad \sum_i x_{ij} = 1 \quad \forall j.$$ Let $t_j$ be the ready time of the knight in slot $j$: the free times of all slots up to $j$, plus that knight’s prep, $$t_j = \sum_i \sum_{l \le j} f_i\, x_{il} \;+\; \sum_i r_i\, x_{ij}.$$ A binary $d_j$ records whether that knight beats the sunset, $d_j = 1$ exactly when $t_j \le 20$, and we maximise how many do: $$\text{maximise} \quad \sum_j d_j \qquad \text{subject to} \qquad d_j = 1 \iff t_j \le 20.$$ The last equivalence is the only modelling care needed; a solver reifies it for us with the finish time as the switched quantity.

from ortools.sat.python import cp_model

FREE = [1, 1, 2, 2, 3, 4, 5, 6]       # free A..H
PREP = [15, 5, 15, 5, 10, 15, 10, 5]  # then wash
DEADLINE = 20

def solve():
    n = len(FREE)
    m = cp_model.CpModel()
    x = {(i, j): m.NewBoolVar("")
         for i in range(n) for j in range(n)}
    for i in range(n):
        m.Add(sum(x[i, j] for j in range(n)) == 1)
    for j in range(n):
        m.Add(sum(x[i, j] for i in range(n)) == 1)
    d = [m.NewBoolVar("") for _ in range(n)]
    for j in range(n):
        freed = sum(FREE[i] * x[i, l]
                    for i in range(n)
                    for l in range(j + 1))
        ready = freed + sum(PREP[i] * x[i, j]
                            for i in range(n))
        m.Add(ready <= DEADLINE).OnlyEnforceIf(d[j])
        m.Add(ready > DEADLINE).OnlyEnforceIf(d[j].Not())
    m.Maximize(sum(d))
    s = cp_model.CpSolver()
    s.Solve(m)
    saved = [chr(65 + i)
             for j in range(n) for i in range(n)
             if s.Value(x[i, j]) and s.Value(d[j])]
    return sorted(saved), int(s.ObjectiveValue())

The solver brings six knights and names them: $A, B, C, D, E, H$. The two left in the dungeon are $F$ and $G$, the pair that are both slow to free and slow to wash. No order saves seven; six is the most the sunset allows, and that group of six is the only one of its size that fits.

The tail is a deadline

There is a cleaner way to see why six, and it dissolves the scheduling into something classical. A knight’s washing runs on its own after he is freed, so it adds nothing to the rescuer’s work; it only sets how early his freeing must finish. To be ready by $20$, a knight with prep $r_i$ must be freed by $$D_i = 20 - r_i,$$ a personal deadline on the one shared resource, the rescuer. The parallel tail has become a due date, and the puzzle is now the textbook problem of sequencing jobs on one machine to maximise how many finish by their due dates.

That problem has a known and quick answer, the Moore–Hodgson rule: take the jobs in due-date order, keep adding them, and whenever the running time passes the current job’s due date, throw out the longest job admitted so far. What survives is a largest on-time set. The due dates here are $$\begin{array}{c|cccccccc} & A & B & C & D & E & F & G & H \\ \hline D_i & 5 & 15 & 5 & 15 & 10 & 5 & 10 & 15 \end{array}$$ and the rule discards $F$ first (free time $4$, due at $5$, the longest among the early-due trio once the clock overruns) and $G$ next, leaving exactly $A, B, C, D, E, H$. The integer program and the hand rule meet at the same six. The model was never wrong to spend its effort on the assignment, but seeing the tail as a deadline is what tells you, without a solver, that six is optimal and which six they are.

Sources. The Sangraal scheduling puzzle is from Martin J. Chlond, Fantasy OR, INFORMS Transactions on Education volume $4$, number $3$ ($2004$), pages $66$–$68$, who takes it from J. R. Partington’s collection Mathematical Puzzles in Fantasy Games. Chlond gives the assignment-and-deadline integer program reproduced here and reports six as the answer. The reduction of the parallel washing to a release-by deadline, and the identification of the result with the one-machine problem of maximising on-time jobs, are this chapter’s; the rule that solves that problem optimally is due to J. M. Moore, An $n$ Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs, Management Science volume $15$ ($1968$), pages $102$–$109$, building on a note of T. J. Hodgson. The unique optimal set of six, and the impossibility of seven, are checked by the model above.