Solving Tents and Trees with bipartite matching: Hall's theorem as a puzzle move

Tents and Trees (テント) in the browser with a bipartite-matching
solver inside. Pitch one tent for every tree on an orthogonally-adjacent
cell; tents never touch — not even diagonally — and each row/column
clue counts its tents. Trees pair off with tents one-to-one, so a
solution is a perfect matching in the bipartite graph trees ×
cells. The solver's star deduction is a vertex-deletion Hall test:
delete a candidate cell and if the maximum matching can no longer
saturate the trees, that cell is a tent in every solution; require a
cell to be matched and if that's infeasible, it's grass. The same
skeleton as Régin's alldifferent filtering — and strong enough that some
bundled boards keep only two of their row/column clues.
Solver-backed puzzle #17.

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

The rules: a solution is a perfect matching

A finished board satisfies:

1. Every tree has a tent on an orthogonally-adjacent cell, and the tree–tent correspondence is one-to-one.
2. No two tents touch, in any of the 8 directions.
3. Every row/column clue equals the number of tents in its line.

Rule 1 is the interesting one. The tent count equals the tree count, and
"which tent belongs to which tree" is an assignment — a perfect matching
in the bipartite graph between trees and tent cells. Unlike the Latin-square
puzzles earlier in this series (Futoshiki, Skyscrapers), the matching isn't
a solving trick bolted on: it's the structure of the puzzle itself.

The cheap rules: spacing, counting, budget

The solver keeps a 4-valued cell state (UNKNOWN / GRASS / TENT / TREE) and
runs the pen-and-paper openers to a fixpoint:

• spacing — a placed tent turns its whole 8-neighbourhood to grass; a tent beside a tent is an immediate contradiction.
• counting — a line that reached its clue grasses the rest; a line where tents + unknowns == clue fills every unknown with a tent.
• budget — exactly one tent per tree, board-wide; both overflow and underflow are contradictions.
• pre-pass — any cell no tree can reach is grass before the player even moves.

Decent, but completely blind to the mid-game question: which trees are
fighting over which cells?

The star: one feasibility oracle, three deductions

Build the bipartite graph between the trees and the cells that could still
hold their tents (state TENT or UNKNOWN, orthogonally adjacent). Every
solution reachable from the current position induces a matching in this
graph that saturates the trees — the tents are the matched cells. So when
feasible() says no, that's a proof about all solutions at once:

// feasible(s, p, exclude?, require?): is there a matching that
//   (a) saturates every tree,
//   (b) covers every placed tent (plus `require`, if given),
//   (c) never uses `exclude`?
export function feasible(s: State, p: Puzzle, exclude = -1, require = -1): boolean

Part (a) is Kuhn's augmenting-path matching from the tree side. Part (b)
uses the Mendelsohn–Dulmage exchange: from an uncovered required cell,
walk alternating paths (any edge out of a cell, the matched edge out of a
tree) until you reach a covered non-required cell, then flip the path —
trees stay saturated, and only a disposable cell loses its partner.

One oracle, three deductions:

if (!feasible(s, p)) return false;             // Hall violation: contradiction
if (!feasible(s, p, i)) s[i] = TENT;           // vertex deletion: trees starve without i
else if (!feasible(s, p, -1, i)) s[i] = GRASS; // no tree to spare for i

• Contradiction — two trees squeezed onto one shared cell (|N(S)| < |S|) is invisible to counting rules but instant here.
• Forced tent — deleting cell i breaks saturation ⇒ every solution uses i. "A tree with a single candidate" is just the trivial case; the same test catches multi-tree Hall-set squeezes with no extra code.
• Forced grass — if a placed tent's only neighbouring tree is t, then t is claimed; a cell that could only pitch for t fails the require-test and must be grass.

If this skeleton looks familiar, it's because it is familiar: Régin's
alldifferent filtering from constraint programming works exactly this way
— compute one maximum matching, then reason about which vertices every / no
maximum matching can use. Industrial CP solvers batch those questions with
an SCC decomposition of the residual graph; on a puzzle-sized board,
per-vertex retests are plenty (the whole 72-test suite runs in 0.2s).

Boards that keep only two clues

The three-way deduction is strong. When the fixpoint stalls, the solver
branches on the first unknown cell and counts solutions, cutting off at
two — count === 1 is a uniqueness proof. The generator authors each
board backwards:

1. Scatter tents at random, rejecting 8-adjacency, and grow a tree on a random free orthogonal neighbour of each — the pairing is a perfect matching by construction.
2. Read off all row and column counts, and check the full-clue board is unique at all (dense campsites occasionally admit a second arrangement; reroll).
3. Greedily delete clues in random order, keeping a deletion only while uniqueness survives.

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

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

The result surprised me: the 6×6 "Clearing" keeps 2 of 12 clues, the
8×8 "Campground" 2 of 16. The row/column numbers nearly vanish — the
tree layout plus the matching structure pin the board almost by themselves.
The solver's strength converts directly into sparser, cleaner puzzles.

Takeaways

• When a puzzle's core constraint is an assignment, model it as the bipartite graph it is — the solver's best move falls out of the structure instead of being pattern-matched onto it.
• One feasible(exclude?, require?) oracle yields contradiction detection, forced tents, and forced grass — Hall's theorem, playable.
• Author boards backwards and delete clues greedily: every surviving clue is load-bearing, and the test suite proves it.

Six boards from 6×6 to 10×10, each with a machine-checked unique solution.
TypeScript, no runtime dependencies, 72 tests. Solver-backed puzzle #17.