Thermometer Puzzles

Aboard of thermometers is to be filled with mercury. Each thermometer lies flat along a row or a column, a bulb at one end and a stem running off the other, and like any thermometer it fills from the bulb: if mercury reaches a cell then every cell between it and the bulb is full too, and if a cell is empty then so is every cell beyond it towards the stem. Around the board, one number to a line, are the counts of filled cells in each row and each column. From the counts alone the level in every thermometer is to be found. The puzzle is a fixture of the smartphone app of the same name, and underneath it is a small integer program.

Fill from the bulb

The rule that mercury fills from the bulb is the whole puzzle, and it is what keeps the model tiny. Walk a thermometer from its bulb to its stem and the cells can only go from full to empty once, never back: a filled cell is never beyond an empty one. So along the thermometer the fill is non-increasing, and the level is fixed by a single threshold, how far the mercury has climbed. The row and column counts pin the thresholds.

Variables

A binary variable holds each cell of the $n \times n$ board, $$x_{ij} \in \{0, 1\}, \qquad x_{ij} = 1 \iff \text{cell } (i, j) \text{ holds mercury}.$$

Constraints

Take each thermometer as the list of its cells from the bulb outward. Between each cell and the next towards the stem the fill cannot rise, which is one inequality per adjacent pair; and the filled cells of each row and column must meet the given counts $r_i$ and $c_j$: $$x_a \ge x_b \quad \text{for consecutive } a, b \text{ along a thermometer},$$ $$\sum_j x_{ij} = r_i \ \ (\forall i), \qquad \sum_i x_{ij} = c_j \ \ (\forall j).$$ There is nothing to optimise; any board meeting the inequalities and the counts is a solution, and a well-set puzzle has exactly one.

A solver

from ortools.sat.python import cp_model

def solve_thermometer(therms, rows, cols):
    n = len(rows)
    m = cp_model.CpModel()
    x = {(i, j): m.NewBoolVar("")
         for i in range(n) for j in range(n)}
    for t in therms:           # fill runs from the bulb out
        for a, b in zip(t, t[1:]):
            m.Add(x[a] >= x[b])    # bulb side filled first
    for i in range(n):
        m.Add(sum(x[i, j] for j in range(n)) == rows[i])
    for j in range(n):
        m.Add(sum(x[i, j] for i in range(n)) == cols[j])
    sol = cp_model.CpSolver()
    sol.Solve(m)
    val = sol.Value
    return [[val(x[i, j]) for j in range(n)] for i in range(n)]

A board

Here are eight thermometers on a five-by-five board, lettered A through H, with each thermometer’s bulb cell underlined: $$\begin{array}{ccccc} \underline{A} & A & A & B & \underline{B} \\ C & D & D & D & \underline{D} \\ C & \underline{E} & \underline{F} & F & F \\ C & E & G & G & \underline{G} \\ \underline{C} & E & \underline{H} & H & H \end{array}$$ The row counts are $4, 2, 1, 3, 3$ from top to bottom, and the column counts $3, 1, 3, 3, 3$ from left to right. Passing the eight thermometers and these counts to the solver fills the board one way only, with a disc for mercury and a dot for an empty cell: $$\begin{array}{ccccc} \bullet & \bullet & \bullet & \cdot & \bullet \\ \cdot & \cdot & \cdot & \bullet & \bullet \\ \cdot & \cdot & \bullet & \cdot & \cdot \\ \bullet & \cdot & \cdot & \bullet & \bullet \\ \bullet & \cdot & \bullet & \bullet & \cdot \end{array}$$ A sweep for other solutions finds none. Each thermometer reads off as a level: A is full to its stem, B holds only its bulb, C is full to two cells, and so on down the eight, and one can check that no other set of levels gives the same twelve marginal counts.

The Thermometer app sits in a paper that lines up six smartphone puzzles as integer programs, and the rest range wider than this one. Kakuro fills cells with digits whose runs sum to clues; Slider walks a block to a target square in the fewest moves, a shortest path; and Flow Free joins coloured dots with disjoint paths that fill the grid, a multi-commodity flow whose paths must be kept connected. Thermometer Puzzles is the gentlest of the six, one binary per cell and a single monotone rule, which is what makes it the natural place to start.

Sources. The Thermometer puzzle, along with Kakuro, the colour-matching games Match 22 and $\infty$ Infinity Loop, the block-sliding Slider, and Flow Free, is modelled as an integer program by Sönke Hartmann, Puzzle—Solving Smartphone Puzzle Apps by Mathematical Programming, INFORMS Transactions on Education volume $18$, number $2$ ($2018$), pages $127$–$141$, which gives the monotone fill condition and the row and column count constraints used here. The eight-thermometer board and its unique solution are the present chapter’s, produced and checked for uniqueness by the model above.