Logical thermometers, beyond temperature

Image by Markus Winkler retrieved from Unsplash

The Thermometer Puzzle is an original logic puzzle where cold calculation meets spatial design. Here, capacity constraints and the physical continuity of fluids come into play.

The goal is to determine which cells of an $m \times n$ grid contain mercury. The grid is completely covered by thermometers of various shapes and lengths. Each thermometer occupies a sequence of adjacent cells (horizontally or vertically) and has a clearly identifiable base or “bulb”.

Formal description of the problem

Given an $m \times n$ grid of cells grouped into different thermometers, we must decide the fill level of each one while respecting the following physical and logical rules:

Row and column requirements: The grid margins indicate exactly how many cells must be filled with mercury in each row and in each column.
Continuous filling (Gravity/Thermometer physics): Thermometers are always filled from the bulb (start) towards the tail end. This implies a strict condition: if a cell contains mercury, all preceding cells in that same thermometer (closer to the bulb) must also be filled. Likewise, if a cell is empty, all subsequent cells in that thermometer must be empty.

Consider the following example of an $8 \times 8$ board:

Would you like to try solving it logically before checking its mathematical modeling?

The magic of this puzzle lies in crossing the information from marginal totals with the directional rigidity of the thermometers. How do we model this apparent “fluid physics” mathematically? By using the elegance of binary linear optimization.

To model this problem, the key lies in how we represent the continuity of the mercury. Instead of creating complex numeric variables for the fill level of each thermometer, we can simply establish a logical dependency relationship between adjacent cells within the same instrument.

Index sets

$\mathcal{I} = \{1, 2, \dots, m\}$: Rows of the board.

$\mathcal{J} = \{1, 2, \dots, n\}$: Columns of the board.

$\mathcal{A} = \{ ((i,j), (r,c)) \in (\mathcal{I} \times \mathcal{J})^2 \}$: Set of ordered cell pairs where cell $(i,j)$ is the immediate predecessor of cell $(r,c)$ within the same thermometer (that is, $(i,j)$ is one step closer to the bulb than $(r,c)$).

Parameters

$R_i$: Exact number of cells that must be filled in row $i \in \mathcal{I}$.

$C_j$: Exact number of cells that must be filled in column $j \in \mathcal{J}$.

Decision variables

$x_{ij} = 1$ if cell $(i,j)$ is filled with mercury, and $0$ if left empty.

This is a pure feasibility problem:

Objective function
\[\min z = 0\]

The physical rules of the game translate into the following linear constraints:

Row and column totals:

The sum of filled cells in each row and column must match the values given in the margins:
\[\sum_{j \in \mathcal{J}} x_{ij} = R_i \quad \forall i \in \mathcal{I}\] \[\sum_{i \in \mathcal{I}} x_{ij} = C_j \quad \forall j \in \mathcal{J}\]

Mercury continuity (Precedence):

If a cell $(r,c)$ contains mercury ($x_{rc} = 1$), its predecessor cell $(i,j)$ in the thermometer must obligatorily be filled ($x_{ij} = 1$). If the predecessor cell is empty ($x_{ij} = 0$), the successor must be empty ($x_{rc} = 0$). This bidirectional logic is modeled with a simple inequality:
\[x_{rc} \leqslant x_{ij} \quad \forall ((i,j), (r,c)) \in \mathcal{A}\]

Variable domains
\[x_{ij} \in \{0, 1\} \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Source code

The Python implementation to solve this problem (along with the equivalent GAMS formulation proposed as an exercise) is available in the GitHub repository.

GitHub Repository: fjmartincampo/ThermometerPuzzle

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.

Logical thermometers, beyond temperature

Formal description of the problem

Challenge solution

Source code

Enjoy Reading This Article?