The math of thermometer puzzles

Each thermometer is a single number

Because mercury fills from the bulb without gaps, a thermometer's whole state is described by one number, its fill level: how many cells, counted from the bulb, contain mercury. A thermometer of length L can be at level 0, 1, 2, … , L. That is L + 1 states, not the 2^L you would get if each cell could be filled independently.

How many arrangements does a grid have?

Multiply the number of states of every thermometer: a grid with thermometers of lengths L₁, L₂, … has (L₁+1)(L₂+1)… possible fillings before any clue is applied. We measured this on puzzles from our generator:

Averages over 8 generated puzzles per size.

The thermometers remove the vast majority of possibilities before you read a single clue. The clues then cut the remaining space down to exactly one arrangement.

The checksum: rows and columns agree

Every mercury cell is in exactly one row and exactly one column. So the row clues and the column clues each add up to the total number of mercury cells:

sum of row clues = sum of column clues = total mercury

This gives you a free check while solving, and a useful extra fact on large puzzles. Battleships has the same property, since its clues are also plain counts (see how the two compare). In our puzzles, mercury fills on average about 52% of a 10×10 grid.

Why the squeeze works: contributions only grow

Fix a line and a thermometer. As the fill level rises, the number of the thermometer's cells in that line can only stay the same or go up. It never goes down. In math terms, the contribution is a monotone function of the level. That is why a lower bound on the contribution becomes a lower bound on the level (fill from the bulb), and an upper bound becomes an upper bound (air toward the tip).

The squeeze and ceiling rule is then just interval arithmetic. If the rest of the line can supply between a and b cells, this thermometer must supply between c − b and c − a. Repeating this over every line until nothing changes is called bounds propagation, and it is exactly how our solver reasons.

When propagation isn't enough

Bounds propagation can stall with cells still open. The next step up is a one-step lookahead: suppose a thermometer is at its lowest (or highest) remaining level, propagate, and if that leads to an impossible line, rule the level out. This is the formal version of the solver's proof by contradiction. Every puzzle on this site is solvable using propagation plus this one-step lookahead. That guarantee is how we know no puzzle needs guessing. The details are in how our puzzles are generated.

Curved thermometers

Everything above holds for curved thermometers too. The only difference is that a curved tube's contribution to a line can grow in several separate jumps as it fills, because it may visit the line more than once. Curved grids also use fewer, longer thermometers (see sizes and variants): a 10×10 curved puzzle averaged 25 thermometers in our sample, versus 32 for straight ones.

Questions