Tank Attack

The Tank Attack puzzle is a small monument to self-reference. A square grid holds a tank in every cell, and each tank is assigned a positive whole number. The number is the tank’s range: a tank of value $k$ attacks, and only attacks, the tanks that sit exactly $k$ cells away along its own row or column. The single rule that makes a board legal binds those two readings of a number together. The value written in a cell must equal the number of tanks that attack it. A tank both declares how far it strikes and records how many strikes land on it, and a solution is a board on which every cell’s two roles agree at once. Chlond set the puzzle as an integer program in the INFORMS Transactions on Education column, and it is a clean lesson in modelling a constraint that refers to its own unknowns.

The position

There are no clues to fill in; the whole board is unknown, and the only input is its size. The task is to find any assignment of values, one to each cell, that satisfies the rule everywhere. A tank may not take the value zero, since a value counts attackers and a legal tank has at least one. On a board of side $n$ the largest useful range is $n - 1$, the span of the board, so every value lies between $1$ and $n - 1$.

The model

Variables

The awkwardness is that whether one tank attacks another depends on the value of the attacker, itself a decision. The standard cure is to make the value an index. For every cell $(i, j)$ and every candidate value $k$, let $x_{ijk} = 1$ when cell $(i, j)$ holds value $k$. Exactly one value sits in each cell, $$\sum_{k=1}^{n-1} x_{ijk} = 1 .$$

The self-referential constraint

With values turned into indicators, attack becomes a lookup. A tank at $(i, p)$ in the same row attacks $(i, j)$ exactly when its value equals the gap between them, that is when $x_{i\,p\,|j-p|} = 1$; likewise down a column. So the number of attackers of $(i, j)$ is a plain sum of indicator variables, and the rule sets it equal to the value in the cell: $$\sum_{p \neq j} x_{i\,p\,|j-p|} \;+\; \sum_{q \neq i} x_{q\,j\,|i-q|} \;=\; \sum_{k=1}^{n-1} k\, x_{ijk} .$$ The left side counts who fires on the cell; the right side reads off the value the cell claims. The same family of $x$ variables appears on both sides, which is the self-reference made linear. There is no objective; a feasible board is a solution.

The solver

from ortools.sat.python import cp_model

def tank(n):
    m = cp_model.CpModel()
    values = range(1, n)                    # a tank's value is 1..n-1
    x = {(i, j, k): m.NewBoolVar("")
         for i in range(n) for j in range(n) for k in values}
    for i in range(n):
        for j in range(n):
            m.Add(sum(x[i, j, k] for k in values) == 1)
    for i in range(n):
        for j in range(n):
            attackers = (
                sum(x[i, p, abs(j - p)] for p in range(n) if p != j)
                + sum(x[q, j, abs(i - q)] for q in range(n) if q != i)
            )
            value = sum(k * x[i, j, k] for k in values)
            m.Add(attackers == value)
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return [[next(k for k in values if s.Value(x[i, j, k]))
             for j in range(n)] for i in range(n)]

The smallest boards have no legal labelling at all: for sides one, two, and three the program is infeasible, and the solver proves it. The four-by-four board has the tidy solution in which every tank carries the value two, each struck by exactly two others two cells away. The six-by-six board solves with the four central cells set to four and the rest to two.

The board the column missed

The five-by-five board is the interesting one. Chlond’s note states that no five-by-five solution exists, listing that size among the impossible ones. The same integer program, run on $n = 5$, disagrees: it returns the board in Figure 26.1, and a direct recount confirms it. The central tank has value four and is struck by exactly four others, the four value-one tanks one step away along its row and column; check any other cell and its value likewise equals its tally of attackers. Enumerating exhaustively, the five-by-five board has not zero solutions but exactly two, the second a near-twin of the first with the threes and fours redistributed. The claim of impossibility is simply mistaken, and the model is what catches it: a formulation faithful enough to solve the puzzle is faithful enough to audit a statement made about it.

Reading the self-reference

What makes the puzzle worth modelling is the shape of its constraint, not its size. Many real problems have this flavour, where a quantity to be decided is defined by a count over the other decisions: a facility’s load is the number of clients who choose it, a node’s degree is the number of edges that select it, a rota’s coverage is the number of staff who pick a slot. The trick that tames Tank Attack, promoting each value to a vector of indicators so that a value-dependent condition becomes a fixed lookup, is the same trick those problems need. Once the value is an index, the circular sentence “my number is how many of you point at me” is just a linear equation, and a solver can be left to find the board on which all of them come true together.

Sources. The puzzle and its integer program follow Martin J. Chlond, Puzzle—A Tank Attack Puzzle, INFORMS Transactions on Education volume $8$, number $3$ ($2008$), pages $149$–$152$ (the integer-programming model there is credited to Adam Atkinson). The puzzle was introduced at the seventh Gathering for Gardner, the biennial Atlanta meeting held in honour of Martin Gardner, and traces to a late-$1990$s international problem-solving competition. The five-by-five board shown here is computed from Chlond’s own model and verified by independent recount. That this recount is faithful to the article’s own rule, and not to a misreading of it, is confirmed by checking that the six-by-six and eight-by-eight boards the article itself prints as solutions satisfy the very same count. Under that shared rule the five-by-five board has not zero solutions but exactly two, correcting the article’s statement that none exists.