Solving Aquarium with subset-sum DP: gravity turns every tank into a chain

Aquarium (アクアリウム) in the browser with a subset-sum solver
inside. The grid is partitioned into aquariums; water poured into one
fills it bottom-up to a single flat waterline that reaches every arm
of the tank (communicating vessels). Row and column clues count water
cells. Gravity makes each aquarium's state space a chain: a tank
spanning d rows has exactly d+1 fillings, totally ordered by
inclusion — so the solver tracks one waterline bitmask per aquarium
instead of cells. The star deduction: a tank's contribution to a clued
line is a pure function of its waterline (all-or-nothing for a row),
so every clue is a subset-sum over the tanks crossing it, filtered
exactly with a prefix/suffix reachable-sum DP — Régin-style support
filtering with a knapsack in place of the matching.
Solver-backed puzzle #18.

🌐 Live demo: https://sen.ltd/portfolio/aquarium/
📦 GitHub: https://github.com/sen-ltd/aquarium

The rules: one waterline per tank

A finished board satisfies:

1. The grid is partitioned into orthogonally-connected aquariums.
2. Water obeys gravity: each aquarium holds one horizontal waterline, and every cell of the tank below it is water, every cell above it air — even in arms that only connect through some other row.
3. Every row/column clue equals the number of water cells in its line.

Rule 2 is the interesting one. Cells are binary (water/air), unlike the
multi-valued domains of the earlier Latin-square puzzles in this series
(Futoshiki, Skyscrapers) — but cell-by-cell reasoning is awkward because
cells of the same tank are strongly correlated. Lift the viewpoint to the
tank and everything collapses.

Gravity turns the domain into a chain

A tank occupying d distinct rows can only be filled in d+1 ways:
choose how many of its occupied rows, counted from the top, stay dry.
And these states are totally ordered by inclusion — lowering the
surface one notch always produces a subset of the previous filling. The
state space is a chain, not a lattice.

So the whole domain of a tank is one small bitmask (at most 11 bits on a
10×10 board):

// state k = "the top k occupied rows are air, the rest water"
export function initialDomains(info: Region[]): number[] {
  return info.map((reg) => (1 << (reg.depth + 1)) - 1);
}

Cell knowledge is a projection of the domain: a cell is known water
when every surviving waterline covers it, known air when none
does. "Everything below the shallowest possible surface is already wet"
becomes two bit tests:

if (mask >> (idx + 1) === 0) s[i] = WATER;               // all k ≤ idx
else if ((mask & ((1 << (idx + 1)) - 1)) === 0) s[i] = AIR; // all k > idx

The star: every clue is a subset-sum

Fix a row r with clue t. If tank a has c cells in that row, its
contribution is c if its waterline is at or below the row, else 0 —
one flat surface cannot wet half a row, so a row's contribution is
all-or-nothing. A column's contribution is the number of the tank's
cells at or below the surface: a monotone step function of the waterline.
Either way it is a pure function of the tank's state, which means:

a clue is a subset-sum over the tanks crossing its line.

That can be filtered exactly with a prefix/suffix reachable-sum DP.
Sums never exceed the line length, so each DP row is a single bitmask
integer:

// prefix[i] / suffix[i]: bitmask of sums reachable by items before / after i
// waterline k of tank a survives ⟺ some s1 ∈ prefix[i], s2 ∈ suffix[i+1]
// give s1 + contrib[k] + s2 === clue
for (let s1 = 0; s1 + v <= clue; s1++) {
  if (((prefix[i] >> s1) & 1) === 0) continue;
  if ((suffix[i + 1] >> (clue - v - s1)) & 1) { ok = true; break; }
}
if (!ok) dom &= ~(1 << k);

This is the skeleton of Régin's support filtering from constraint
programming — alldifferent asks "is there a maximum matching using this
value?", Aquarium asks "is there a completion of this knapsack using this
waterline?". Per line it is as strong as enumerating the whole line: any
conclusion derivable from that line alone falls out.

The cross-line power comes free. A tank crosses several rows and columns
at once, so one line's verdict cascades through gravity into every
other line the tank touches: if row 0's clue forces a tank full, all its
cells in every row become water, and every other DP's input changes. Run
to a fixpoint, this solves most positions outright; when it stalls, a
search branches on the tank with the fewest surviving waterlines and
counts solutions, using count === 1 as a proof of uniqueness.

Boards authored backwards

The generator starts from the answer:

1. Partition the grid into connected tanks by random frontier growth (scatter seeds, then repeatedly hand a random unassigned cell to a random assigned neighbour).
2. Pour a random waterline into each tank and read off all row and column counts — checking the full-clue board is uniquely solvable at all (small tanks occasionally admit a second filling; reroll).
3. Greedily delete clues in random order, keeping a deletion only while the engine still proves exactly one solution.

What survives is a locally minimal clue set — dropping any single
remaining clue breaks uniqueness, and the test suite verifies exactly that
for every clue of every board:

it('every surviving clue is load-bearing', () => {
  expect(hasUniqueSolution(chopped)).toBe(false);
});

The tank shapes are themselves strong constraints, so the numbers thin out
dramatically: the 6×6 "Rockpool" keeps 5 of 12 clues, the 10×10
"Deepwater" 10 of 20.

Takeaways

• Find the chain. Gravity collapses an exponential-looking cell space into d+1 totally-ordered states per tank. Choosing the tank (not the cell) as the variable is the whole game.
• Clues over chains are knapsacks. When each variable's contribution to a constraint is a pure function of its state, a counting clue is a subset-sum — and reachable-sum DP gives exact, cheap support filtering.
• Régin's skeleton generalizes. Compute one feasibility structure, then ask which states every / no solution can use. The oracle can be a matching (Tents), a permutation enumeration (Skyscrapers), or a DP.
• Author puzzles backwards. Fill the tanks, read all clues, greedily delete while uniqueness survives — every surviving clue is load-bearing.

Six boards from 6×6 to 10×10, each with a machine-checked uniqueness
proof; 60 vitest tests. TypeScript, no runtime dependencies.
Solver-backed puzzle #18.