Chain Reaction

A chain-reaction board is a grid of coloured shapes, and the puzzle is to thread a single route through it that visits every cell exactly once. The route starts on the cell marked with a cross. Each step moves along a row or a column, never on a diagonal, and may leap over any number of cells; the one rule is that the shape it lands on must share either the colour or the shape of the cell it left. A route that visits every cell once is a Hamiltonian path, and a Hamiltonian path is the travelling salesman problem with the return leg removed. That makes the chain reaction the gentlest possible doorway into the most famous problem in combinatorial optimisation, and into the one idea that tames it: the subtour-elimination constraint. The treatment here follows Gail DePuy’s note in the INFORMS Transactions on Education puzzle column.

The puzzle

The board in Figure 18.1 is a $3 \times 3$ grid of red and blue circles and squares. Number the cells $1$ to $9$, left to right and top to bottom, so cell $1$ is the top-left cell (the start, marked $\times$) and cell $9$ is the bottom-right. A move from cell $i$ to cell $j$ is permitted when $i$ and $j$ lie in the same row or the same column and their symbols agree in colour or in shape. The task is to order all nine cells into one route, beginning at cell $1$, that uses only permitted moves.

An assignment relaxation

Collect the permitted moves into a $0$-$1$ matrix: $A_{ij} = 1$ when a move from cell $i$ to cell $j$ is allowed. Because the route need not return to its start, introduce one artificial node, numbered $10$, that every cell may move to and that stands for “the route ends here.”

Variables

For every allowed move let $$Y_{ij} \in \{0, 1\}, \qquad Y_{ij} = 1 \iff \text{the route steps from cell } i \text{ to cell } j,$$ with $j$ ranging over the cells and the terminator $10$.

Constraints

Every cell is left exactly once, and every cell other than the start is entered exactly once; the terminator is entered exactly once: $$\begin{align} \sum_{j} A_{ij}\, Y_{ij} &= 1, & i &\in \{1, \ldots, 9\}, \\ \sum_{i} A_{ij}\, Y_{ij} &= 1, & j &\in \{2, \ldots, 9\}, \\ \sum_{i} Y_{i, 10} &= 1. && \end{align}$$ There is no quantity to minimise; any feasible assignment is a candidate. This is the classical assignment relaxation of the travelling salesman problem, and it has a famous defect: nothing in it forbids the solution from breaking into several disjoint loops. Solve the relaxation for this board and the cells do split, into a route through some of them and one or more closed loops, or subtours, through the rest.

Subtour elimination

The cure is due to Dantzig, Fulkerson, and Johnson. Whenever a solution contains a subtour on a set $S$ of cells, no valid route can use $|S|$ moves that all stay inside $S$, so we add the cut $$\sum_{i \in S}\sum_{j \in S} A_{ij}\, Y_{ij} \;\le\; |S| - 1,$$ which breaks that loop, and re-solve. Each pass may reveal a fresh subtour; we repeat until a single route survives. The program below runs the loop, adding the smallest subtour it finds as a cut each time.

from ortools.sat.python import cp_model

GRID = ["RC", "RC", "RS",        # red/blue circle/square, row by row
        "BC", "RS", "BC",
        "BS", "BC", "BS"]
N, START, T = 9, 0, 9            # cells 0..8; node 9 terminates the route

def rook(i, j):
    return i != j and (i // 3 == j // 3 or i % 3 == j % 3)

def allowed(i, j):               # same row/column, sharing colour or shape
    return rook(i, j) and (GRID[i][0] == GRID[j][0]
                           or GRID[i][1] == GRID[j][1])

def chain_reaction():
    arcs = [(i, j) for i in range(N) for j in range(N) if allowed(i, j)]
    arcs += [(i, T) for i in range(N)]
    cuts = []
    while True:
        m = cp_model.CpModel()
        Y = {a: m.NewBoolVar(str(a)) for a in arcs}
        for i in range(N):                       # leave every cell once
            m.Add(sum(Y[a] for a in arcs if a[0] == i) == 1)
        for j in range(N):                       # enter every cell but start
            if j != START:
                m.Add(sum(Y[a] for a in arcs if a[1] == j) == 1)
        m.Add(sum(Y[a] for a in arcs if a[1] == T) == 1)
        for S in cuts:                           # subtour-elimination cuts
            m.Add(sum(Y[a] for a in arcs
                      if a[0] in S and a[1] in S) <= len(S) - 1)
        s = cp_model.CpSolver()
        s.Solve(m)
        succ = {a[0]: a[1] for a in arcs if s.Value(Y[a])}
        succ[T] = START
        seen, cycles = set(), []
        for n0 in list(succ):
            if n0 in seen:
                continue
            cyc, n = [], n0
            while n not in seen:
                seen.add(n); cyc.append(n); n = succ[n]
            cycles.append(cyc)
        subtours = [c for c in cycles if T not in c]
        if not subtours:
            path, n = [], START
            while n != T:
                path.append(n + 1); n = succ[n]
            return path
        cuts.append(set(min(subtours, key=len)))

The assignment relaxation alone returns disjoint loops; three rounds of subtour elimination are needed before the board resolves into the single route $$1, \; 3, \; 9, \; 6, \; 4, \; 7, \; 8, \; 2, \; 5,$$ which is unique, and which Figure 18.1 traces. Each arrow keeps to a row or a column and joins two cells of a common colour or shape.

Why this is the travelling salesman

Strip away the colours and the chain reaction is bare TSP machinery: the cells are cities, the permitted moves are edges, and a route is a Hamiltonian path. The assignment relaxation followed by subtour-elimination cuts is exactly the method Dantzig, Fulkerson, and Johnson used in $1954$ to solve a forty-nine-city tour by hand, the calculation that founded the field. What keeps this instance small is the colour-and-shape rule, which deletes most edges before the solver begins; a fully connected board would admit a route between almost any pair of cells, and the number of subtour constraints that might be needed grows explosively with the board. That explosion is the travelling salesman’s difficulty in miniature, met here on nine squares instead of forty-nine cities.

Sources. The puzzle and its integer-programming treatment follow Gail W. DePuy, Puzzle—Chain-Reaction: A Puzzle to Demonstrate TSP Formulation, INFORMS Transactions on Education volume $10$, number $1$ ($2009$), pages $41$–$44$. The chain-reaction puzzle itself is Andrea Gilbert’s, from her clickmazes collection ($1997$); the board used here is a re-authored instance whose unique route matches the one DePuy solves. The assignment-plus-subtour-elimination method is George Dantzig, Ray Fulkerson, and Selmer Johnson, Solution of a Large-Scale Traveling-Salesman Problem, Operations Research volume $2$ ($1954$), pages $393$–$410$; the alternative compact formulation that avoids enumerating subtours is due to Miller, Tucker, and Zemlin ($1960$).