The Knights Exchange

Two white knights sit in the bottom corners of a three by three board, two black knights in the top corners. Swap them, white for black, moving as knights move, one knight at a time, in as few moves as you can. The puzzle is old: Paolo Guarini set it down in $1512$, and it is discussed in Arabic manuscripts a thousand years before that. Its charm for an integer programmer is not the answer, which is sixteen, but the gap between two ways of reaching it. One natural model grinds for hours; another, built on a single observation about the board, returns the same sixteen in the blink of an eye. The puzzle is a lesson in the cost of a formulation.

The puzzle

Number the cells of the board one to nine, left to right and bottom to top, so the bottom row is $1, 2, 3$ and the top row is $7, 8, 9$. A knight leaps in an L: two cells one way and one cell across. The white knights start on cells $1$ and $3$, the black knights on $7$ and $9$. A move picks up one knight and sets it on any cell a knight’s leap away that is empty. The goal is the colour-swapped board, white knights on $7$ and $9$, black knights on $1$ and $3$, and we want the shortest sequence of moves that reaches it.

Two knights of the same colour are interchangeable: it does not matter which white knight ends on $7$ and which on $9$, only that white ends on top and black on the bottom. That small freedom matters later, because it shrinks the problem.

A board that is secretly a ring

Everything turns on one fact about the centre. From the middle cell $5$ a knight has nowhere to land: every L-leap runs off the board. Cell $5$ is dead, never entered and never left, so the knights move among the eight cells around the rim. Now list the leaps available from each rim cell and a surprise appears. Cell $1$ reaches only $6$ and $8$; cell $6$ reaches only $1$ and $7$; cell $7$ reaches only $2$ and $6$; and so on around. Every rim cell has exactly two knight-neighbours, and following them threads all eight cells onto a single closed loop, $$1 - 6 - 7 - 2 - 9 - 4 - 3 - 8 - 1 .$$ The knight graph of the three by three board is one ring of eight. The left of Figure 31.1 draws the leaps on the board, where they make the familiar eight-pointed star; the right straightens that star into the ring it really is.

On a ring, knights cannot pass one another. A knight only ever steps to an adjacent cell along the loop, and to step past a neighbour it would have to land where that neighbour sits, which is forbidden. So the four knights keep their cyclic order forever. Read the colours around the ring at the start, skipping the empty cells: white, black, black, white. Read the target the same way: black, white, white, black. The second is the first turned by two places around the ring. Since the order is frozen, the only way to turn the arrangement by two pieces is to march every knight the same way around the loop until it has advanced two occupied places, which is four cells of travel. Four knights, four cells each, and the count writes itself: $$4 \times 4 = 16 .$$ No formulation is needed to find the answer; the ring hands it over. What the formulations do is confirm it, and in confirming it teach the lesson the puzzle was set to teach.

The model that fits the ring

The clean way to optimise a sequence of moves is to make each whole position a node and each move an arc, then ask for a shortest path. A position is fixed by where the two white knights sit and where the two black knights sit; because same-colour knights are interchangeable, we store each colour’s pair as an unordered set. There are eight live cells, so the number of positions is $\binom{8}{2}\binom{6}{2} = 28 \times 15 = 420$, and joining each position to those one legal move away gives $1{,}920$ arcs. A shortest path from the start position to the swapped one is the fewest moves.

This is a minimum-cost flow: send one unit from the start node to the target node, every arc costing one, and the cheapest feasible flow traces the shortest path. The flow-conservation law, what enters a node leaves it, except for the one unit created at the start and absorbed at the target, is the whole model.

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

def adj(c):                              # knight leaps from cell c
    r, k = (c - 1) // 3, (c - 1) % 3
    out = []
    for dr, dc in ((1,2),(1,-2),(-1,2),(-1,-2),
                   (2,1),(2,-1),(-2,1),(-2,-1)):
        rr, kk = r + dr, k + dc
        if 0 <= rr < 3 and 0 <= kk < 3:
            out.append(rr * 3 + kk + 1)
    return out

CELLS = [c for c in range(1, 10) if adj(c)]   # cell 5 is dead, dropped
A = {c: adj(c) for c in CELLS}

def positions():                         # (white pair, black pair), sorted
    for w in combinations(CELLS, 2):
        free = [c for c in CELLS if c not in w]
        for b in combinations(free, 2):
            yield (w, b)

def moves(s):                            # positions one legal move away
    w, b = s
    occ = set(w) | set(b)
    for grp, other, white in ((w, b, True), (b, w, False)):
        for i, cell in enumerate(grp):
            for nb in A[cell]:
                if nb not in occ:
                    ng = tuple(sorted((grp[1 - i], nb)))
                    yield (ng, other) if white else (other, ng)

def knight_swap():
    S = list(positions())
    arcs = [(s, t) for s in S for t in moves(s)]
    src, snk = ((1, 3), (7, 9)), ((7, 9), (1, 3))
    m = cp_model.CpModel()
    x = {a: m.NewBoolVar("") for a in arcs}
    out, inc = {}, {}
    for a in arcs:
        out.setdefault(a[0], []).append(a)
        inc.setdefault(a[1], []).append(a)
    for s in S:                          # flow conservation, +1/-1 at ends
        net = 1 if s == src else (-1 if s == snk else 0)
        m.Add(sum(x[a] for a in out.get(s, []))
              - sum(x[a] for a in inc.get(s, [])) == net)
    m.Minimize(sum(x.values()))
    sol = cp_model.CpSolver()
    sol.Solve(m)
    return len(S), len(arcs), round(sol.ObjectiveValue())

The graph has its $420$ positions and $1{,}920$ moves, and the shortest path is $16$. The solve is instant: the model is small because the state space is small, and the state space is small because the ring has so few arrangements.

The natural model, and why it strains

A student meeting the puzzle rarely reaches first for positions and arcs. The instinct is to index by time: let $x_{t,i,j}$ be $1$ when knight $i$ stands on cell $j$ at step $t$, let $z_{t,i}$ mark that knight $i$ moves at step $t$, fix the start, demand the swap by some horizon $T$, and minimise the moves $\sum_{t,i} z_{t,i}$. The rules become linear constraints: one cell per knight and at most one knight per cell at every step; a knight that moves lands on a legal neighbour; at most one knight moves per step; a knight that does not move stays put. It is a faithful model, and it is honest about the puzzle.

It is also far heavier. Its variables multiply the horizon by the knights by the cells, and the horizon must be guessed large enough to contain the answer. On this small board a modern solver still clears it, but the author who set the puzzle reports the same formulation, in a different solver, running more than four hours and swallowing gigabytes before it returned the sixteen the ring gives for free. The arithmetic of the model, not the difficulty of the puzzle, is what hurt.

def knight_swap_timeindexed(T=17):
    KN = (1, 2, 3, 4)                    # 1,2 white; 3,4 black
    start = {1: 1, 2: 3, 3: 7, 4: 9}
    m = cp_model.CpModel()
    x = {(t,i,j): m.NewBoolVar("")
         for t in range(1, T+1) for i in KN for j in CELLS}
    z = {(t,i): m.NewBoolVar("") for t in range(1, T) for i in KN}
    for t in range(1, T+1):
        for i in KN:
            m.Add(sum(x[t,i,j] for j in CELLS) == 1)
        for j in CELLS:
            m.Add(sum(x[t,i,j] for i in KN) <= 1)
    for t in range(1, T):
        for i in KN:
            for j in CELLS:
                m.Add(sum(x[t+1,i,jp] for jp in A[j]) >= z[t,i] + x[t,i,j] - 1)
                m.Add(x[t+1,i,j] >= x[t,i,j] - z[t,i])
                m.Add(x[t+1,i,j] <= x[t,i,j] + z[t,i])
        m.Add(sum(z[t,i] for i in KN) <= 1)
    for i in KN:
        m.Add(x[1,i,start[i]] == 1)
    m.Add(x[T,1,7] + x[T,1,9] == 1)      # white knights end on top
    m.Add(x[T,2,7] + x[T,2,9] == 1)
    m.Add(x[T,3,1] + x[T,3,3] == 1)      # black knights end on the bottom
    m.Add(x[T,4,1] + x[T,4,3] == 1)
    m.Minimize(sum(z.values()))
    sol = cp_model.CpSolver()
    sol.Solve(m)
    return round(sol.ObjectiveValue())

Both models return sixteen, as they must. The difference is not in the answer but in the work: one searches a graph of four hundred positions, the other a lattice of time, knights, and cells, and the second is larger by orders of magnitude for nothing gained.

What the puzzle teaches

There is no unique way to model a problem, and the choice is not cosmetic. The same sixteen moves cost hours under one formulation and milliseconds under another, and the cheaper one came from looking at the board until it stopped being a board and became a ring. A good model is often a reduction: throw away the dead centre, notice that order on a ring is fixed, collapse interchangeable pieces into sets, and what remained was a shortest path, one of the most tractable problems in all of optimisation. The instinct to index everything by time is natural and almost always available, and almost always the wrong place to stop. The knights’ real lesson is to spend a little longer on the board before reaching for the solver, because the structure you find there is worth more than any amount of machinery laid on top of a structure you missed.

Sources. The puzzle and the contrast of its two formulations follow Mehdi Iranpoor, Knights Exchange Puzzle—Teaching the Efficiency of Modeling, INFORMS Transactions on Education volume $21$, number $2$ ($2021$), pages $108$–$114$, published open access under a Creative Commons Attribution licence. The optimal value of sixteen moves, the time-indexed binary program, the minimum-cost-flow reformulation, and its $420$-node, $1{,}920$-arc state graph are the author’s; both are reproduced here by the models above, which agree on sixteen, and the $420$ and $1{,}920$ are reproduced exactly. The puzzle is Guarini’s, recorded in his manuscript of $1512$ and traced to Arabic sources of around AD $840$; see Miodrag Petković, Famous Puzzles of Great Mathematicians (American Mathematical Society, Providence, $2009$). That the knight graph of the three by three board is a single eight-cycle, and the rotation argument it licenses, are classical; they are set out in Anany and Maria Levitin, Algorithmic Puzzles (Oxford University Press, New York, $2011$).