Knights, Knaves, and the Lady

Raymond Smullyan’s puzzle books turn formal logic into story. An island is peopled by knights, who only ever speak the truth, and knaves, who only ever lie; a prisoner faces a row of doors, each bearing a sign that may be true or false, with a lady behind one and a tiger behind another. To solve such a puzzle is to find the one assignment of types and contents under which every statement carries exactly the truth value its speaker is bound to. That is a constraint-satisfaction problem, and its statements are logical propositions, so the question is whether ordinary integer programming, whose native language is the linear inequality, can express “this sentence is true if and only if its speaker is a knight.” It can, and the device that makes it possible is the indicator variable. The puzzles below follow Chlond and Toase’s study of Smullyan in the INFORMS Transactions on Education column.

Indicator variables: logic as linear constraints

The whole chapter rests on one construction. Suppose a linear expression $F(x)$ over binary variables is known to lie between integer bounds $L \le F(x) \le U$, and we want a binary variable $\delta$ to record whether a linear condition on $F$ holds. For the condition $F(x) \ge n$, the coupling $\delta = 1 \iff F(x) \ge n$ is enforced by the pair $$\begin{align} F(x) - (U - n + 1)\,\delta &\le n - 1, \\ F(x) - (n - L)\,\delta &\ge L. \end{align}$$ For the opposite condition $F(x) \le n$, the coupling $\delta = 1 \iff F(x) \le n$ is enforced by $$\begin{align} F(x) + (n + 1 - L)\,\delta &\ge n + 1, \\ F(x) + (U - L)\,\delta &\le n + U - L. \end{align}$$ Once propositions have indicator variables attached, the logical connectives between them become linear relations among those indicators. Writing $\delta_X$ for the indicator of proposition $X$, $$\lnot X : \delta_X = 0, \qquad X \land Y : \delta_X + \delta_Y = 2, \qquad X \lor Y : \delta_X + \delta_Y \ge 1,$$ $$X \rightarrow Y : \delta_X \le \delta_Y, \qquad X \leftrightarrow Y : \delta_X = \delta_Y.$$ These equivalences are catalogued in H. P. Williams’s Model Building in Mathematical Programming. A knight-or-knave puzzle is then a small program: one binary per person for the type, one per statement for its truth value, and the rule that a person’s type variable equals the truth variable of what they say.

Werewolves

In Smullyan’s forest, each inhabitant is a knight or a knave, and some are also werewolves; a werewolf may be of either type. We interview three inhabitants, $A$, $B$, and $C$, and are told that exactly one of them is a werewolf. They say:

$A$: “I am a werewolf.” $B$: “I am a werewolf.” $C$: “At most one of the three of us is a knight.”

The task is to classify all three.

Variables

For each person $p \in \{A, B, C\}$ let $x_p = 1$ if $p$ is a knight (a truth-teller) and $0$ if a knave, and let $w_p = 1$ if $p$ is the werewolf.

Constraints

Exactly one werewolf gives $w_A + w_B + w_C = 1$. A person is a knight precisely when their statement is true, so for $A$ and $B$, whose claim “I am a werewolf” has truth value $w_A$ and $w_B$, the coupling is the direct equality $$x_A = w_A, \qquad x_B = w_B.$$ $C$’s claim is the proposition “at most one knight,” that is $x_A + x_B + x_C \le 1$. Taking $\delta = x_C$ with $F = x_A + x_B + x_C$, bounds $L = 0$, $U = 3$, and $n = 1$, the $F \le n$ template gives $$x_A + x_B + 3x_C \ge 2, \qquad x_A + x_B + 4x_C \le 4,$$ which force $x_C = 1$ exactly when at most one of the three is a knight. There is nothing to optimise; any feasible point is a solution.

A solver in twenty lines

from ortools.sat.python import cp_model

def werewolves_two():
    m = cp_model.CpModel()
    x = {p: m.NewBoolVar(p) for p in "ABC"}        # knight = 1
    w = {p: m.NewBoolVar("w" + p) for p in "ABC"}  # werewolf = 1
    m.Add(sum(w.values()) == 1)
    m.Add(x["A"] == w["A"])                         # A: "I am a werewolf"
    m.Add(x["B"] == w["B"])                         # B: "I am a werewolf"
    # C: "at most one knight"  ->  x_C = 1 iff x_A + x_B + x_C <= 1
    m.Add(x["A"] + x["B"] + 3 * x["C"] >= 2)
    m.Add(x["A"] + x["B"] + 4 * x["C"] <= 4)
    s = cp_model.CpSolver()
    s.Solve(m)
    role = {p: ("knight" if s.Value(x[p]) else "knave") for p in "ABC"}
    wolf = next(p for p in "ABC" if s.Value(w[p]))
    return role, wolf

The solution is unique: $A$ and $B$ are knaves and $C$ is a knight, and the werewolf is $C$. The reasoning the program compresses is short. If $A$ were a knight, his statement would make him the werewolf, and likewise for $B$; but then there would be two knights, $A$ and $B$, contradicting $C$ if $C$ too were a knight and leaving the werewolf count wrong in every case. The only consistent reading has $A$ and $B$ lying about being werewolves, $C$ telling the truth that at most one of them (namely $C$) is a knight, and $C$ carrying the single werewolf. Figure 17.1 records it.

A companion puzzle, Werewolves IV, keeps the forest but changes the testimony: we are told exactly one of the three is a werewolf and that the werewolf is a knight, and now $A$ says “at least one of the three of us is a knave” while $B$ says “$C$ is a knight.” The werewolf constraint becomes $x_p \ge w_p$ for each $p$; $A$’s claim $x_A + x_B + x_C \le 2$ is linearised by the same $F \le n$ template, and $B$’s claim is the equality $x_B = x_C$. The model returns a unique answer: $A$ is a knight, $B$ and $C$ are knaves, and $A$ is the werewolf.

The lady or the tiger

Smullyan’s other world is a prison whose trials Smullyan borrowed from Frank Stockton. A prisoner faces several doors; behind each is a lady or a tiger; he would rather find the lady. Each door bears a sign, and in any given trial a rule fixes how the signs relate to the truth. In the second trial there are two rooms, and the rule is that the two signs are either both true or both false. The signs read:

Door $1$: “At least one of these rooms holds a lady.” Door $2$: “A tiger is in the other room.”

Variables and constraints

Let $x_i = 1$ if room $i$ holds the lady and $0$ if it holds the tiger, and let $t_i = 1$ if the sign on door $i$ is true. Door $1$ asserts $x_1 + x_2 \ge 1$, so with $\delta = t_1$, $F = x_1 + x_2$, $L = 0$, $U = 2$, $n = 1$, the $F \ge n$ template gives $$x_1 + x_2 - 2t_1 \le 0, \qquad x_1 + x_2 - t_1 \ge 0.$$ Door $2$ asserts that the other room, room $1$, holds the tiger, which is $1 - x_1$, so $t_2 = 1 - x_1$. The trial’s rule is the biconditional $t_1 = t_2$.

A solver in fifteen lines

from ortools.sat.python import cp_model

def second_trial():
    m = cp_model.CpModel()
    x = {i: m.NewBoolVar(f"lady{i}") for i in (1, 2)}  # lady = 1
    t = {i: m.NewBoolVar(f"t{i}") for i in (1, 2)}     # sign true = 1
    # Door 1: "at least one lady"  ->  t1 = 1 iff x1 + x2 >= 1
    m.Add(x[1] + x[2] - 2 * t[1] <= 0)
    m.Add(x[1] + x[2] - t[1] >= 0)
    # Door 2: "a tiger is in the other room" = room 1 holds the tiger
    m.Add(t[2] == 1 - x[1])
    m.Add(t[1] == t[2])             # this trial: both signs share a truth value
    s = cp_model.CpSolver()
    s.Solve(m)
    return {i: ("lady" if s.Value(x[i]) else "tiger") for i in (1, 2)}

The unique solution puts the tiger in room $1$ and the lady in room $2$, with both signs true, so the prisoner should open door $2$ (Figure 17.2). The trap the puzzle sets is the reading in which both signs are false; the model shows that reading is infeasible, because a false door $1$ sign would mean neither room holds the lady, and then door $2$’s sign, also false, would deny the tiger in room $1$, leaving room $1$ with neither occupant.

A logical labyrinth

The same machinery scales to Smullyan’s hardest trial in this vein, a labyrinth of nine doors. Each room now holds a lady, a tiger, or nothing; only one room holds the lady; the sign on the lady’s door is true; the signs on the tiger doors are false; and the signs on empty rooms may be either. The nine signs refer to one another and to the room contents, so the model carries a content variable $x_{i, j}$ for door $i$ and outcome $j \in \{\text{lady}, \text{tiger}, \text{empty}\}$ and a truth variable $t_i$ for each sign, with every sign linearised by the templates above.

What makes the labyrinth worth the climb is not its size but a twist that integer programming states exactly. As posed, the puzzle has more than one feasible solution, so the prisoner cannot deduce where the lady is. He can only when he is also told that room $8$ is not empty. Adding the single constraint $x_{8, \text{empty}} = 0$ collapses the feasible region to one point. The missing fact is, quite literally, a missing constraint, and the puzzle is the rare riddle whose punchline is that information and constraint are the same thing. The full nine-door model is a chapter of its own; here it stands as the destination the indicator variable was built to reach.

Sources. The integer-programming treatment of these puzzles follows Martin J. Chlond and Cath M. Toase, IP Modeling and the Logical Puzzles of Raymond Smullyan, INFORMS Transactions on Education volume $3$, number $3$ ($2003$), pages $1$–$12$. The werewolf puzzles are from Raymond Smullyan, What Is the Name of This Book? (Prentice-Hall, $1978$); the lady-or-tiger trials are from Smullyan, The Lady or the Tiger? (Alfred A. Knopf, $1982$), which builds on Frank R. Stockton’s $1882$ story of that name. The indicator-variable couplings and the linear forms of the logical connectives are catalogued in H. P. Williams, Model Building in Mathematical Programming (Wiley, $1999$).