DEV Community: SEN LLC

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

SEN LLC — Mon, 20 Jul 2026 23:17:19 +0000

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:

Every tree has a tent on an orthogonally-adjacent cell, and the tree–tent correspondence is one-to-one.
No two tents touch, in any of the 8 directions.
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:

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.
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).
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.

Solving Skyscrapers by projecting permutations: a line has n! futures, not n^n

SEN LLC — Sun, 19 Jul 2026 23:19:30 +0000

Skyscrapers (ビルディング) in the browser with an exact
line-projection solver inside. Fill an n×n grid with building heights so
every row and column holds 1..n exactly once, while every edge
clue counts the buildings visible from that side — taller buildings
hide everything shorter, so the visible ones are exactly the running
maxima. Humans open with a staircase rule (clue c caps the cell k
steps in at n−c+1+k); the solver's star is stronger: a line of a Latin
square is a permutation, so it has at most n! completions, not
n^n. Enumerate the permutations consistent with the current masks, keep
those matching both end clues, and intersect each cell with the
union of the survivors — the tightest line-local conclusion possible,
quietly subsuming hidden singles, naked pairs, and the staircase itself.
Solver-backed puzzle #16.

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

The rules: visible = running maxima

A finished board satisfies:

Every row and every column holds each height 1..n exactly once (a Latin square).
Every edge clue equals the number of buildings visible from its side.

"Visible" has a one-line definition:

/** Buildings a viewer sees looking down the line: the running maxima. */
export function visible(heights: number[]): number {
  let seen = 0, max = 0;
  for (const h of heights) {
    if (h > max) { max = h; seen++; }
  }
  return seen;
}

In [2, 4, 1, 3] you see two buildings — 2, then 4; the 1 and the 3 hide in
the 4's shadow. The tallest building n is visible from everywhere. As in
Futoshiki, the unknown is a value in 1..n, so each cell is a candidate
bitmask.

The opening: a staircase of ceilings

The pencil-and-paper classic. Put height v in the cell k steps (0-based)
from a clue c, and every building taller than v must stand behind it —
work out how many "steps" that leaves in front and you get the ceiling
v ≤ n − c + 1 + k:

// initialState: a clue c carves staircase ceilings into its first c−1 cells
if (clue === 1) state[ordered[0]] &= 1 << (n - 1); // c=1: nearest cell IS n
for (let k = 0; k < clue - 1; k++) {
  state[ordered[k]] &= fullMask(n - clue + 1 + k);
}

c = 1 means one building visible: the nearest cell is the tower n itself.
c = n staircases the whole line into ascending 1, 2, …, n. Cheap and
satisfying — but strictly an opening. It sees nothing of the midgame.

The star: a line is a permutation, so project it

Here is the observation this puzzle rewards. When you want stronger
propagation you usually add named patterns one by one (hidden pairs, X-wing,
…). But a Skyscrapers line has decisive structure: a line of a Latin
square is a permutation of 1..n. A row doesn't have n^n possible
completions — it has at most n!. Even at n = 7 that's 5040. You can just
enumerate them.

export function projectLine(state: Uint16Array, view: View, n: number) {
  const union = new Array<number>(n).fill(0);
  // DFS over permutations consistent with the current masks.
  // The front clue prunes as we go: too many maxima already — cut;
  // not enough "headroom" left (remaining cells, remaining heights) — cut.
  // The back clue is checked at each leaf by a reverse scan.
  // Surviving permutations OR their values into union[i]…
  for (let i = 0; i < n; i++) {
    if (union[i] === 0) return false;   // no permutation survives: contradiction
    state[cells[i]] = union[i];         // intersect with the survivors' union
  }
}

Intersecting each cell with the union of surviving permutations is,
mathematically, the projection of the line constraint onto that cell —
the tightest conclusion any line-local reasoning can reach. Which means:

hidden singles, naked pairs, and the staircase itself are all subsumed, silently;
every line-local pattern that doesn't have a name yet gets "used" anyway.

Contradiction detection falls out for free. Opposite clues on one line can
sum to at most n + 1 (the tallest building is counted from both sides).
Put 3 + 3 on a 4-line: the staircase leaves every mask non-empty, yet
projection instantly reports zero surviving permutations:

it('detects a line with no surviving permutation', () => {
  const bad = puz([...], { left: ring('3...'), right: ring('3...') });
  expect(propagate(initialState(bad)!, geom(4), bad)).toBe(false);
});

What projection cannot do

Projection is complete per line, not per board. Rows constrain columns
and columns constrain rows back, so the projections are iterated to a
fixpoint; when even that stalls, a fewest-candidates backtracking
search branches, re-propagates, and counts. solveAll(p, 2) is a complete
enumeration that stops at two solutions, so length === 1 is a proof of
uniqueness.

Boards are authored by deletion

The generator works answer-first: build a random Latin square, read all
4n view clues off its edges (the board is trivially unique at that point),
then greedily delete clues in random order — givens first — keeping a
deletion only while the engine still proves exactly one solution. What
survives is locally minimal: removing any single remaining clue breaks
uniqueness, and the test suite checks that on every board:

it('is minimal: dropping the first view clue breaks uniqueness', () => {
  expect(hasUniqueSolution(dropped)).toBe(false);
});

Six boards, 4×4 through 7×7. The 4×4 pins a unique skyline with just
four view clues.

Takeaways

A Skyscrapers clue is a non-local aggregate — a count of running maxima
— that refuses to decompose into per-edge clamps the way Futoshiki's signs
did. What worked instead was a domain-structure observation: a line is a
permutation, so its futures number n!, not n^n, and enumerate → filter →
project (intersect with the survivors' union) becomes the strongest
line-local inference at a practical cost. The staircase opening is subsumed
by it; the cross-line remainder falls to fixpoint iteration and a
fewest-candidates search that proves all six boards unique. 56 tests.
Solver-backed puzzle #16.

Solving Futoshiki with bounds propagation: one-edge rules, chain-length conclusions

SEN LLC — Sat, 18 Jul 2026 23:12:38 +0000

Futoshiki (不等号 / "inequality") in the browser with a
bounds-propagation solver inside. Fill an n×n grid so every row and
column holds each value 1..n exactly once while every < / >
sign between neighbouring cells tells the truth. Unlike the shading
puzzles earlier in this series, the unknown is a value in 1..n, so a
cell is a candidate bitmask and the rules shrink sets: duplicate
eviction, hidden singles, and — the star — a bounds rule that clamps
one floor and one ceiling per sign. That rule only ever looks at one
edge, yet run to a fixpoint it performs interval arithmetic over whole
inequality chains: the cell k steps up a chain ends up with floor k+1, a
global, chain-length conclusion no single rule ever computed. Solver-backed
puzzle #15.

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

The rules, and a change of model

A Futoshiki board is n×n. A finished board satisfies:

Every row and every column holds each of 1..n exactly once (a Latin square).
Every sign between two orthogonally adjacent cells is true (a < b means a really is smaller).

Clues come in two kinds — a few given digits, and the inequality
signs in the gutters. Most of the bundled boards are signs only.

The shading puzzles before this one (Nurikabe, LITS, Hitori…) had a one-bit
unknown per cell, so a three-valued cell was enough. Futoshiki's unknown is a
value, so each cell becomes a candidate set, stored as a bitmask in
one integer:

export function fullMask(n: number): number {
  return (1 << n) - 1;          // all of 1..n possible
}
export function minVal(mask: number): number {
  return 32 - Math.clz32(mask & -mask);   // smallest candidate = floor
}
export function maxVal(mask: number): number {
  return 32 - Math.clz32(mask);           // largest candidate = ceiling
}

The point of the encoding: minVal / maxVal read directly as the ends of
an interval.

Three propagation rules

Duplicate — a solved cell evicts its value from its row and column; an
emptied mask is a contradiction:

const bit = 1 << (v - 1);
for (const m of g.peers[i]) {
  if (state[m] & bit) {
    state[m] &= ~bit;
    if (state[m] === 0) return false;
  }
}

Hidden single — if a value has exactly one home left in a line, it moves
in; zero homes is a contradiction.

Bounds — a sign a < b translates into two clamps: a may only keep
values below b's current ceiling, and b only values above a's
current floor:

for (const { lo, hi } of p.ineqs) {
  const clampedLo = state[lo] & below(maxVal(state[hi]));      // lo < max(hi)
  const clampedHi = state[hi] & above(minVal(state[lo]), g.n); // hi > min(lo)
  ...
}

All three run to a fixpoint. No guessing.

The show: one edge per step, whole chains per fixpoint

Each application of the bounds rule looks at one edge. Iterated to a
fixpoint, something bigger emerges: interval arithmetic over the whole
inequality graph.

Take a < b < c < d across a 4×4 row. Pass one: a < b lifts b's floor to
2, b < c lifts c's to 3, c < d lifts d's to 4 — while the ceilings
tighten the other way and a drops to 1. In general the cell k steps from
the bottom of a chain gets floor k+1, and k steps from the top gets ceiling
n−k. A chain of n−1 signs pins all n cells outright, and the test suite
states exactly that:

it('derives chain-length floors from pairwise clamps alone', () => {
  // a < b < c < d: every rule step saw one sign,
  // yet the fixpoint pins the whole row to 1234.
  const p = puz(['....', '....', '....', '....'], [
    { lo: 0, hi: 1 }, { lo: 1, hi: 2 }, { lo: 2, hi: 3 },
  ]);
  const s = initialState(p);
  expect(propagate(s, geom(4), p)).toBe(true);
  expect([0, 1, 2, 3].map((i) => solvedVal(s[i]))).toEqual([1, 2, 3, 4]);
});

In constraint-programming terms this is bounds consistency enforced
edge-by-edge rather than full arc consistency: it never looks at holes in the
middle of a candidate set, but inequality is an order constraint, so floors
and ceilings carry all the strength you need. Cheap local clamps, run to a
fixpoint, flood bounds across chains, forks and joins of the sign DAG.

Contradiction detection falls out of the same machinery for free — put four
< signs in a 4-value board and some floor demands a 5, emptying a mask:

it('contradicts a chain longer than the board allows', () => {
  // 4 strict increases need 5 distinct values — impossible in a 4×4.
  expect(propagate(initialState(p), geom(4), p)).toBe(false);
});

Search and the uniqueness proof

When propagation stalls, the solver branches on the fewest-candidates
cell, tries values in ascending order, and re-propagates. solveAll(p, 2) is
a complete enumeration that stops at two solutions, so length === 1 is a
proof of uniqueness.

Boards are authored by deletion

The generator (tools/generate.mts) works answer-first. Build a random Latin
square by backtracking, read the true sign off every adjacent pair — all
2n(n−1) of them — at which point the board is trivially unique. Then
greedily delete clues in random order, keeping a deletion only while the
engine still proves exactly one solution. Givens go first, so the boards end
up sign-driven (two of the six have no givens at all).

What survives is a locally minimal clue set: removing any single
remaining clue breaks uniqueness. The test suite checks that claim on every
board:

it('is minimal: dropping any one sign breaks uniqueness', () => {
  const dropped: Puzzle = { n, givens, ineqs: ineqs.slice(1) };
  expect(hasUniqueSolution(dropped)).toBe(false);
});

Not just "this board is unique" but "every remaining sign is
load-bearing." 55 tests in all.

Takeaways

Futoshiki is this series' first multi-valued domain — cells became
candidate bitmasks and propagation became set-shrinking. The star is the
bounds rule: a cheap clamp that sees one edge at a time, yet whose fixpoint
performs interval arithmetic across entire inequality chains, producing
global, chain-length conclusions (floor k+1 at height k) that no single rule
ever computed. Duplicate eviction and hidden singles cover the Latin side; a
fewest-candidates search proves uniqueness; and the bundled boards are thinned
from the full sign set until every surviving clue carries weight.
Solver-backed puzzle #15.

Solving Hitori with constraint propagation: the puzzle where propagation can't even start

SEN LLC — Fri, 17 Jul 2026 23:15:27 +0000

Hitori (ひとりにしてくれ / "leave me alone") in the browser with a
constraint-propagation solver inside. Every cell carries a number; you
keep (white) or shade (black) each one so that kept numbers never
repeat in a row or column, shaded cells never touch side-to-side, and
the kept cells stay one connected region. The unknown is the usual
one bit per cell, the model the usual three-valued cell — but on an untouched
board every dynamic rule is starved: the duplicate rule needs a white
cell to exist, the adjacency rule needs a black one, connectivity needs both.
Pure propagation is a no-op on move one. The only ways in are the
puzzle's two textbook openings — sandwich and pair — each a one-step
case analysis whose branches agree, which is exactly the condition that
lets a case split masquerade as a sound propagation rule. Solver-backed
puzzle #14.

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

The rules, and the usual model

A Hitori grid is R×C with a number in every cell. A finished board keeps or
shades each cell so that:

Among the kept cells, no number repeats in any row or column.
Shaded cells are never orthogonally adjacent.
The kept cells form one orthogonally-connected region.

Same unknown as Nurikabe — one bit per cell — so the model is the same
three-valued cell, shrunk by sound, guess-free implications only:

export const UNKNOWN = 0;
export const WHITE = 1;   // kept
export const BLACK = 2;   // shaded

Three dynamic rules write themselves:

duplicate — a cell decided WHITE evicts every copy of its number from its row and column (two kept copies in one line is a contradiction).
adjacency — a cell decided BLACK whitens all four neighbours (two adjacent blacks is a contradiction).
cut cell — an UNKNOWN cell whose shading would disconnect the whites must itself be WHITE. No trial assignment needed: flood the non-black graph with that cell removed and see whether every white is still reached.

The trap: propagation has no seed

Here is where Hitori differs from every earlier puzzle in this series. A fresh
board is all UNKNOWN. The duplicate rule fires off an existing white, the
adjacency rule off an existing black, the connectivity check needs two whites —
so none of the three can fire on move one. Run them to a fixpoint and
nothing happens. In Nurikabe or Akari the printed clues pin cells from the
start; Hitori's clues (the numbers) directly decide no cell's colour.

The test suite states it outright:

it('is a clean no-op on a board with no pattern', () => {
  const p = puz(['12', '21']);
  const s = initialState(p);
  expect(propagate(s, geom(2, 2), p)).toBe(true);
  expect([...s]).toEqual([UNKNOWN, UNKNOWN, UNKNOWN, UNKNOWN]);
});

The way in: case splits whose branches agree

Human solvers open every Hitori the same way, with two textbook patterns — and
implementing them is where the design clicks. Both are case analyses, yet
both are legitimate propagation rules, because every branch reaches the same
conclusion.

Sandwich — a ? a in one line. Shade the middle and both flanking as
survive as kept duplicates. So whichever a lives, the middle cell is
white:

// sandwich: a ? a  =>  the middle cell is white.
for (let k = 1; k + 1 < line.length; k++) {
  if (p.values[line[k - 1]] === p.values[line[k + 1]]) {
    if (!assign(state, line[k], WHITE)) return false;
  }
}

Pair — an adjacent a a. Not both kept (duplicate), not both shaded
(adjacent) — so exactly one survives. You don't know which, but you do know
the line now owns a kept a, so every other a in that line is black:

// pair: a a  =>  every other a in the line is black.
for (const m of line) {
  if (p.values[m] === v && !assign(state, m, BLACK)) return false;
}

Both rules are static — their conclusions depend only on the printed numbers —
but they still run inside the fixpoint, because a "must be white" landing on an
already-black cell is a contradiction worth catching. The moment they inoculate
the board with its first blacks and whites, the dynamic rules cascade: a black
whitens its neighbours, a white evicts its twins, and the cut-cell rule rescues
whites about to be walled in.

An aside: Hitori never asks for a reason to shade

One rule subtlety only implementation made obvious: there is no minimality
constraint. Nothing requires a shaded cell to deserve shading — any shading
that breaks no rule is a solution. A duplicate-free 2×2 board therefore has
five solutions (keep everything, or shade any single cell; the two diagonal
double-shadings die by disconnection):

const p = puz(['12', '21']);
expect(solveAll(p, 10).length).toBe(5);

So a well-posed board must be unique the hard way: every gratuitous extra
shade has to die by adjacency or disconnection. That lands squarely on the
generator.

Search, and the uniqueness proof

When propagation stalls, the search branches on the UNKNOWN cell with the
most decided neighbours, tries BLACK then WHITE, and re-propagates.
solveAll(p, 2) is a complete enumeration that stops at two solutions, so
length === 1 is a genuine uniqueness proof:

export function hasUniqueSolution(p: Puzzle): boolean {
  return solveAll(p, 2).length === 1;
}

Boards are authored answer-first

The generator (tools/generate.mts) writes the solved shading before the
numbers. Scatter black cells (never adjacent, whites kept connected), then give
the white cells a shuffled Latin square's values — row/column uniqueness
among the whites holds by construction. Each black cell then copies a
value from a white cell in its own row or column, so every shaded cell has a
visible reason: keep it and its line gains a duplicate. Finally the engine must
prove exactly one solution — which, per the aside above, includes proving
that every do-nothing extra shade dies. The tests re-check all of it per board:
the authored shading is legal, every black has its excuse, and the solver
recovers exactly the authored answer. 45 tests, 5×5 through 10×10.

Takeaways

Hitori hands you back the humble cell-bit unknown — and then starves the
propagator: no clue decides a cell, so sound dynamic rules alone cannot make
the first move. The openings that unlock it are the puzzle's two classic
patterns, and the reason they're classic is structural: each is a one-step
case split whose branches agree, the exact shape a case analysis must have to
count as propagation. Seed the board with them, let duplicate / adjacency /
cut-cell chain to a fixpoint, and a fewest-options search proves each bundled
board has exactly one answer. Solver-backed puzzle #14.

Solving Shikaku with constraint propagation: when the unknown is a rectangle, not a cell

SEN LLC — Thu, 16 Jul 2026 23:12:53 +0000

Shikaku (四角に切れ, "divide by squares") in the browser with a
constraint-propagation solver inside. Cut the grid into rectangles: every
rectangle holds exactly one number, and that number is its area. This
is where the previous twelve solvers' model breaks. They all put the unknown
in a cell — a colour bit, a digit domain, an edge bit. Shikaku's unknown is
coarser: which rectangle does each number take? Enumerate those candidates
up front and the puzzle collapses into a plain exact cover, with
propagation running over sets of rectangles instead of cells. Two sound,
mutually dual rules (only-coverer and forced-cell) run to a
fixpoint, then a fewest-candidates search proves uniqueness. Solver-backed
puzzle #13.

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

The rules, and the logic that follows

A Shikaku grid is R×C with some cells carrying a number. A finished board
cuts it into axis-aligned rectangles so that:

every rectangle contains exactly one number;
a rectangle's area equals that number;
the rectangles tile the grid — every cell covered exactly once.

Why the cell model is the wrong one here

Ask "what colour is this cell?" and Shikaku gives a useless answer: every cell
is covered, always. The information isn't in the cell — it's in the cut. So
the domain moves up a level, from the cell to the clue:

// every box that contains the clue, has exactly its area, and eats no other clue
export function candidatesFor(p: Puzzle, cell: number): Rect[] {
  for (let h = 1; h <= n; h++) {
    if (n % h !== 0) continue;   // only integer h×w factorisations
    const w = n / h;
    ...
  }
}

A 12 clue has at most six shapes (1×12, 2×6, 3×4, 4×3, 6×2, 12×1), each with a
handful of placements — a domain of a few dozen at worst. Small enough to
enumerate once and then just filter, which is the whole trick.

Note the third condition doing quiet work: a candidate that would swallow
another clue never enters the domain at all. The closer the numbers sit, the
smaller every domain starts out.

The two rules are duals

The entire propagation is two sound rules — and they're mirror images:

// only-coverer: a cell nobody else can reach pins its clue
if (who.size === 0) return false;              // orphan cell — nothing can cover it
if (who.size === 1) /* kill k's candidates that miss c */

// forced-cell: a cell one clue always takes is closed to the rest
for (const c of common) /* kill every OTHER clue's candidate covering c */

One says a cell needs someone; the other says a cell allows only one.
Together they're enough — and the rule you'd reach for first, "a clue down to a
single candidate commits it, and everything overlapping dies", needs no code
at all. It falls out of forced-cell: a singleton domain's intersection is its
own rectangle, so every cell of that box closes to everyone else automatically.

propagate() runs both to a fixpoint, returning false the moment a clue
loses every candidate or a cell loses every coverer.

When logic stalls: search that proves uniqueness

Some boards need a guess. The search branches on the clue with the fewest
surviving candidates, pins it, re-propagates, and counts. A complete assignment
is accepted only when isSolved() agrees — an independent validator that
re-checks areas, containment, overlap and full coverage from scratch, sharing no
logic with the propagator, so a solver bug can't cancel out a validator bug.

export function hasUniqueSolution(p: Puzzle): boolean {
  return solveAll(p, 2).length === 1;
}

solveAll enumerates up to a limit; hasUniqueSolution stops at two, and the
tests assert every bundled puzzle stops at exactly one.

There's also a nearly-free sanity check worth doing before any of it: the clues
must sum to the area of the grid. One pass, and it rejects a whole class of
malformed boards before a single rectangle is enumerated.

const total = p.clues.reduce((a, b) => a + b, 0);
if (total !== p.R * p.C) return [];

Puzzles are solver-verified, not hand-keyed

Each board is authored as its solved tiling — one letter per cell naming its
rectangle, uppercase on the cell that carries the number:

'aaabBcc'      region 'b' is a 1×2 box, so its clue reads 2
'aAadDCc'      region 'a' is a 3×3 box, so its clue reads 9
'aaaeecc'

Both halves of a clue are derived: its position is the uppercase cell, its
number is the area of that letter's region. Nothing is typed twice, so a
clue cannot drift out of sync with its answer. Better, a drawing that isn't a
real tiling — an L-shaped region, a region with two numbers, a region with none —
fails to parse at all:

if (h * w !== cells.length) {
  throw new Error(`board "${name}" region "${key}" is not a filled rectangle`);
}

The generator (tools/generate.mts) cuts a grid into random rectangles and tries
several clue placements per tiling — which cell in a box carries the number
changes the puzzle completely, and that turned out to be the search axis that
mattered — keeping a board only if the solver proves a single solution. The
tests re-solve every board and assert it recovers exactly the drawn tiling:

expect(hasUniqueSolution(b.puzzle)).toBe(true);        // exactly one answer
expect(coverMap(solveAll(b.puzzle, 2)[0], b.puzzle))   // and it's the drawn one
  .toEqual(b.cover);

One more generator knob that earned its keep: penalise 1×1 rectangles
(weight 1 vs 3). A board of single cells is perfectly unique and perfectly
boring. Same discipline as the Nurikabe, Masyu, Hashiwokakero, Star Battle,
Kakuro and Akari entries: ship your levels through your solver. The bundled
boards run 5×5 up to 10×10.

A small UI lesson

Colouring the rectangles, I first cycled hue by k * 47 % 360. Red came up.
Red was already the colour for an illegal rectangle, so a perfectly good box
rendered as an error. Fixed by exiling the hue from the red band:

// Kept inside 40°..330° — red is reserved for illegal boxes and must not collide.
const hue = 40 + ((k * 67) % 290);

Generated palettes don't just look bad when they collide — they break meaning.

Takeaway

The real lesson of Shikaku is that the granularity you put the unknown at
decides how hard the puzzle is. Put it in the cell and you get a useless
answer: everything is covered, always. Move it to the cut — which rectangle
does each number take — and the domain becomes a small enumerable set, the puzzle
collapses into exact cover, and you need exactly two rules, which are duals of
each other, and which contain the obvious third rule for free. Get the model
right and the code gets shorter. Solver-backed puzzle #13.

Solving Nurikabe with constraint propagation: three-valued cells, a reachability flood, and a uniqueness proof

SEN LLC — Thu, 16 Jul 2026 01:57:37 +0000

Nurikabe (ぬりかべ / "plaster wall") in the browser with a
constraint-propagation solver inside. Every cell is white (part of a
numbered island) or black (the sea), and the solver keeps a
three-valued cell — UNKNOWN / WHITE / BLACK — running sound
deductions to a fixpoint before it ever guesses. Four rules feed each other:
the pool rule (no 2×2 all-black), the sealed island (a white region the
size of its clue seals its border), the merge / over-size check, and the
one that does the heavy lifting — a reachability flood that expands every
clue outward and blacks out any cell no clue can still reach. Each bundled
board is authored as its own solved sea, so the clues are read off the answer
and can never drift. Solver-backed puzzle #12.

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

The rules, and the logic that follows

A Nurikabe grid is R×C with some cells carrying a number. A finished board
paints every cell white or black so that:

each island is one orthogonally-connected white block holding exactly one number, and its size equals that number;
islands never touch orthogonally (a black cell always separates them);
all black cells form one connected sea with no 2×2 pool.

The unknown here is simple — one bit per cell, white or black — but the rules
tangle connectivity (islands and sea) with counting (island sizes) with a
local shape ban (the 2×2 pool). We model the cell three-valued (UNKNOWN
until decided) and shrink it with strict, guess-free deductions.

The pool rule and sealed islands

Two are immediate. No 2×2 window may be all black, so three blacks force the
fourth white, and four blacks is an instant contradiction. And a white region
whose size already equals its clue is finished — every unknown cell touching
it becomes sea:

if (cells.length === clue) {
  for (const cell of cells)
    for (const nb of g.nbrs[cell])
      if (state[nb] === UNKNOWN) { state[nb] = BLACK; changed = true; }
}

The same region scan rejects two clues merged into one region, or a region grown
past its number.

The reachability flood

This is the crux. A cell can be white only if some clue's island could still
grow to include it. So flood every clue outward through unknown cells, spending
one unit of its remaining budget (clue − current size) per unknown cell
entered, and black out every cell no flood reaches:

for (const { id, cells, clue } of clued) {
  const budget = clue - cells.length;          // cells this island may still add
  // BFS from the island, cost = unknown cells spent; mark everything ≤ budget
  ...
}
for (let i = 0; i < g.N; i++) {
  if (reach[i]) continue;
  if (state[i] === UNKNOWN) { state[i] = BLACK; changed = true; }   // unreachable → sea
  else if (state[i] === WHITE && region[i] === -1) return false;    // stranded island
}

The subtle part is soundness. For "unreachable ⇒ black" to be safe, the
flood must never miss a genuinely reachable cell — its reach set has to be a
superset of the truth. So the flood is deliberately generous: it lets
orphan white cells be crossed for free and ignores the finer "can't sit next to
another island" refinement. Over-counting reach only ever leaves fewer cells
to black out, so every cell it does black is provably sea. Being generous is
what makes the deduction correct.

propagate() runs the pool rule, sealing, the region checks and the flood to a
fixpoint, returning false the instant any rule contradicts.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracker branches on the most constrained
unknown cell (the one touching the most already-decided cells), tries it BLACK
then WHITE, and lets propagation prune. A complete assignment is accepted only
when isSolved() holds: every island exact and clued, the sea one connected
region, and no 2×2 pool.

export function hasUniqueSolution(p: Puzzle): boolean {
  return solveAll(p, 2).length === 1;
}

solveAll branches BLACK/WHITE on undecided cells — a complete
enumeration — pruned only by sound propagation. It stops at two solutions, so
the "unique" it reports is real.

Puzzles are solver-verified, not hand-keyed

Each board is authored as its solved grid. The generator
(tools/generate.mts) is sea-first: it grows one connected sea by a random
walk that never completes a 2×2 pool, then reads the leftover white
components off as islands — so connectivity and pool-freeness hold by
construction, not by rejection sampling. It drops one number per island and
keeps the clue set only if the solver proves a single solution. The tests
re-solve every board and assert it recovers exactly the drawn sea:

expect(hasUniqueSolution(b.puzzle)).toBe(true);                 // exactly one answer
expect(Array.from(solve(b.puzzle)!)).toEqual(                  // and it's the drawn one
  Array.from(b.solution),
);

One tuning note worth its own line: raising the sea's coverage produces
smaller, more numerous islands, which means more clues, which makes a
single-clue-per-island board far likelier to be uniquely solvable — and cheaper
to verify. That one knob was the difference between the 10×10 generating in
seconds versus not at all. Same discipline as the Masyu, Hashiwokakero, Star
Battle, Kakuro and Akari entries: ship your levels through your solver. The
bundled boards run 5×5 up to 10×10.

Takeaway

Nurikabe looks like a shading puzzle but it's really a reachability puzzle.
Once the unknown is a three-valued cell, "no pool" and "sealed island" are cheap
local rules, "one connected sea" is a leaf check, and the real deductions come
from a generous flood that blacks out everything no clue can claim — sound
precisely because it over-counts. Branch the most-constrained cell, prune with
that logic, and the search proves uniqueness while staying complete.
Solver-backed puzzle #12.

Solving Masyu with constraint propagation: an edge model, local patterns, a closure guard, and a uniqueness proof

SEN LLC — Wed, 15 Jul 2026 10:41:55 +0000

Masyu (ましゅ / "pearls") in the browser with a single-loop
constraint-propagation solver inside. Three ideas carry it. (1) The
unknowns are edges, not cells — each grid edge is one bit, in the loop or
not; every cell has degree 0 or 2, and a pearl's degree is exactly 2.
(2) Each cell's edges must match one of its legal local patterns — a white
○ runs straight, a black ● turns, a plain cell is unused or bent — and a
black additionally forces the cell one step beyond each arm to run straight.
All strict implications, never guesses. (3) A closure guard kills any loop
that closes before it has swallowed every pearl. Each bundled board is authored
as its own solved loop, so the pearls are read off the answer and can never
drift. Solver-backed puzzle #11.

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

The rules, and the logic that follows

A Masyu grid is R×C. Some cells hold a white ○ or black ● pearl. You
draw one closed loop between orthogonally adjacent cell centres that never
crosses or reuses itself, and:

White ○ — the loop passes straight through, and turns in at least one of the two cells immediately before/after it.
Black ● — the loop turns here, and runs straight through the cell immediately on each side.

Everything starts with picking the right unknown. For Nonogram or Star Battle
the unknown is a cell; for Masyu the loop is a set of edges, so we make the
edges the unknowns — R*(C-1) horizontal + (R-1)*C vertical, each
UNKNOWN / ON / OFF. A cell's degree (its ON edges) is 0 or 2; a
pearl's is exactly 2. Two strict, guess-free implications fall out.

Local patterns

Every cell's ON edges must equal one of the local patterns allowed for it,
which we enumerate up front:

Plain: unused (degree 0) or any two edges (degree 2)
White ○: only its two collinear edges — {left,right} or {up,down}
Black ●: one horizontal + one vertical — {L,U} {L,D} {R,U} {R,D}

Propagation is then trivial: keep only the patterns consistent with the decided
edges, and whenever the survivors all agree on an edge, force it.

const ok = g.patterns[cell].filter((pat) => {
  for (const e of inc) {
    const inPat = pat.includes(e);
    if (inPat && state[e] === OFF) return false;
    if (!inPat && state[e] === ON) return false;
  }
  return true;
});
if (ok.length === 0) return false;                 // contradiction
for (const e of inc) {                              // agreed on by all → forced
  if (state[e] !== UNKNOWN) continue;
  const anyOn = ok.some((p) => p.includes(e));
  const anyOff = ok.some((p) => !p.includes(e));
  if (anyOn && !anyOff) state[e] = ON;
  else if (anyOff && !anyOn) state[e] = OFF;
}

"White runs straight" and "black turns" are both captured purely by these
patterns. A pearl squeezed against the border with no room to run straight/turn
simply has zero surviving patterns — a contradiction.

Black's "straight on each side" as an edge rule

The half of the black rule about neighbours running straight drops out as an
edge implication: if a black's arm is ON, the edge one cell further along
must be ON too (that neighbour runs straight). If the outer edge is OFF, the
arm can't point that way.

if (state[inner] === ON) {
  if (outer < 0 || state[outer] === OFF) return false;   // no room to run straight
  if (state[outer] === UNKNOWN) { state[outer] = ON; changed = true; }
} else if (state[inner] === UNKNOWN && (outer < 0 || state[outer] === OFF)) {
  state[inner] = OFF;                                     // this arm is impossible
}

White's "turn immediately before/after" depends on a neighbour's shape — it's
non-local, so it's checked at the leaf, not during propagation.

The closure guard

This is the loop-specific crux. A closed cycle can never grow again. So the
instant ON edges form a finished loop, it must already contain every pearl and
every ON edge — any earlier closure would spawn a second loop and is a dead
branch.

for (const [root, hasOpen] of compHasOpen) {
  if (hasOpen) continue;                                       // still growing
  if ((compEdges.get(root) ?? 0) / 2 !== totalOn) return false; // ON edges outside it
  for (let cell = 0; cell < cells; cell++)
    if (g.pearls[cell] !== NONE && find(cell) !== root) return false; // a pearl left out
}

propagate() runs all of this to a fixpoint, then applies the closure guard.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracker branches on the edge that extends an
existing loop fragment (a cell already holding one ON edge), tries it ON then
OFF, and lets propagation prune. A complete assignment is accepted only when
isSolution() holds: every cell degree 0 or 2, every pearl rule (including the
non-local white/black neighbour checks), and the ON edges form exactly one
cycle.

export function hasUniqueSolution(puzzle: Puzzle): boolean {
  return solveAll(puzzle, 2).length === 1;
}

The search branches ON/OFF on every undecided edge — a complete
enumeration — pruned only by sound propagation and the closure guard. So the
"unique" it reports is real.

Puzzles are solver-verified, not hand-keyed

Each board is authored as its solved loop plus the pearls that loop earns.
The generator (tools/generate.mts) grows one rectilinear loop from a 2×2 cycle
by repeatedly bumping a straight segment outward into two empty cells (every
bump preserves a single self-avoiding loop), reads every legal white/black
spot off the finished loop, then greedily drops pearls while the solver still
proves a single solution. The tests re-solve every board and assert it recovers
exactly the drawn loop:

expect(hasUniqueSolution(b.puzzle)).toBe(true);
expect(edgeKey(solve(b.puzzle)!)).toBe(edgeKey(b.solution)); // and it's the drawn loop

Same discipline as the Hashiwokakero, Star Battle, Kakuro and Akari entries: ship
your levels through your solver. The bundled boards run 5×5 up to 7×7.

Takeaway

The whole puzzle unlocks once you move the unknown from cells to edges. Then
"white straight / black turn" becomes each cell's local pattern, "black runs
straight on both sides" becomes an edge implication, and "one closed loop"
becomes a closure guard plus a single-cycle check at the leaf. Branch the
undecided edges, prune with sound logic, and the search proves uniqueness while
staying complete. Solver-backed puzzle #11.

Solving Star Battle with Constraint Propagation and a Uniqueness Proof

SEN LLC — Mon, 13 Jul 2026 23:17:06 +0000

Star Battle (Doppelstern / スターバトル), the star-placement logic puzzle,
built for the browser with a constraint-propagation solver inside. Three
hinges: (1) the unknowns are one bit per cell — star or empty — and
each of the board's 3n lines (n rows, n columns, n irregular regions) is a
count-exactly-k constraint. When a line's stars are all placed, its rest is
struck empty; when the only way to reach k is to use every open cell, they
are all stars; and a placed star empties its eight neighbours. Each step is
a strict implication, never a guess. (2) When logic stalls, a backtracking
search branches on a cell in the line with the fewest open cells, lets
propagation prune, and counts solutions. (3) Every bundled board is drawn
as its own solved grid, so the region shapes — the only clue — are read off
the answer and can't drift. Solver-equipped puzzle #10.

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

The rules, and the logic that follows

A Star Battle grid is an n×n board carved into exactly n irregular
regions. You place stars so that:

Rows — every row holds exactly k stars (k is 1 or 2).
Columns — every column holds exactly k stars.
Regions — every region holds exactly k stars.
Spacing — no two stars touch, not even diagonally.

The first move is to notice what the unknowns actually are. Each cell is a single
bit — star or empty — so we track its state as UNKNOWN / STAR /
EMPTY and shrink it with two rules that are strict deductions, never guesses.

Exact count

Every row, column and region is a count-exactly-k line. Count what is already
placed and what is still open, and both extremes are forced. If the stars are all
placed (placed === k), every open cell in the line is empty. If the only
way to reach k is to use every open cell (placed + open === k), they are all
stars.

if (placed > g.stars) return { ok: false, forced };        // too many → contradiction
if (placed + open < g.stars) return { ok: false, forced }; // can't reach k → contradiction
if (placed === g.stars) {              // line full → clear the rest
  for (const cell of unit) if (state[cell] === UNKNOWN) set(cell, EMPTY);
} else if (placed + open === g.stars) { // only enough cells left → all stars
  for (const cell of unit) if (state[cell] === UNKNOWN) set(cell, STAR);
}

The nice part is that the three kinds of line don't need special-casing: rows,
columns and regions are all just a list of cell ids with the same
exactly-k constraint, so one loop handles every unit.

Spacing

The moment a star is placed, its eight neighbours become empty — and two
stars that touch are an immediate contradiction:

for (let cell = 0; cell < state.length; cell++) {
  if (state[cell] !== STAR) continue;
  for (const nb of g.neighbors[cell]) {
    if (state[nb] === STAR) return { ok: false, forced };   // adjacent → contradiction
    if (state[nb] === UNKNOWN) set(nb, EMPTY);
  }
}

propagate() runs both rules to a fixpoint, recording the order cells are
pinned — which is exactly what the demo's Hint replays, one guess-free
deduction at a time.

When logic stalls: search that proves uniqueness

Plenty of boards — the 2-star ones especially — need a guess. The backtracking
solver picks a cell in the still-unsatisfied line with the fewest open cells
(the tightest place a single decision prunes), fixes it to STAR then EMPTY,
and lets propagation prune each branch:

function chooseCell(state, g) {
  let best = -1, bestOpen = Infinity;
  for (const unit of g.units) {
    let placed = 0, open = 0, firstOpen = -1;
    for (const cell of unit) {
      if (state[cell] === STAR) placed++;
      else if (state[cell] === UNKNOWN) { open++; if (firstOpen < 0) firstOpen = cell; }
    }
    if (placed >= g.stars || open === 0) continue;   // skip satisfied lines
    if (open < bestOpen) { bestOpen = open; best = firstOpen; }
  }
  return best;
}

A complete assignment is accepted only when isSolved() holds — every line has
exactly k stars and no two stars touch. solveAll enumerates up to a limit;
hasUniqueSolution stops at two, and the test suite asserts every bundled puzzle
stops at exactly one:

export function hasUniqueSolution(puzzle: Puzzle): boolean {
  return solveAll(puzzle, 2).length === 1;
}

This is what makes Star Battle interesting to generate. There are no number
clues at all — the region shapes are the only clue. So "solvable by pure
logic" and "has a unique solution" are properties the region carving has to earn,
which is why the generator leans on the solver as its oracle.

Puzzles are solver-verified, not hand-keyed

Every board is authored as the solved grid, one character per cell. The
letter names the region (A, B, C, …); an uppercase letter is an
empty cell, the same letter lowercase marks the star:

BBaCC      row 0: region B, B, a STAR in region A, C, C
bBBCC      row 1: a STAR in region B, then B, B, C, C
BDBcC      …
BdDCC
BDDDe

The region map and the star solution are read off the same grid, and because a
region's cells all share one letter, the shapes are exact by construction. The
generator (tools/generate.mts) first places a legal star pattern (k per row
and column, none touching), then seeds one region per group of stars and grows
the regions outward by flood-fill — since every star is a seed, growth only
ever adds empty cells, so each region keeps exactly k stars. It keeps a board
only if the regions are all connected and the solver proves the layout admits a
single solution. The tests re-solve every finished board and assert it recovers
exactly the drawn stars:

expect(hasUniqueSolution(b.puzzle)).toBe(true);   // exactly one answer
expect(stars(sol)).toEqual(stars(b.solution));    // and it's the drawn map

Same discipline as the Hashiwokakero, Kakuro, Nonogram and Akari entries: ship
your levels through your solver. The six bundled boards run 5×5 (1★) up to 10×10
(2★).

The UI

The board is one <svg>. Cells are region-tinted rects, with a thick border
drawn only where two cells of different regions meet (compare neighbouring
region ids — that's the whole test). Click cycles a cell empty → star (★) →
× (an empty pencil-mark) → empty. A player-facing verdict() mirrors the
solver's rules but reports which things are wrong — stars that touch, lines
with the wrong count — for live highlighting, and declares a win only when every
line holds exactly k stars with none adjacent.

src/star.ts        — pure engine: 3n exact-count lines + 8-way spacing, sound
                     propagation to a fixpoint, region connectivity check,
                     fewest-options backtracking, uniqueness count
src/star.test.ts   — 43 vitest cases
src/puzzles.ts     — 6 solved grids, all generator-made and solver-verified
src/main.ts        — SVG UI: region-tinted cells, thick region borders, the
                     star / × / empty cycle, Hint, animated Solve
tools/generate.mts — placement + region-growth generator that authors unique boards

No runtime dependencies; TypeScript throughout. MIT-licensed — clone it, read
the engine, lift the exact-count + spacing pattern.

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

This is part of a series of 100+ small, sharp, open-source builds by
SEN, LLC. Solver-equipped puzzle #10 — after Hashiwokakero,
Kakuro, Akari, Slitherlink, Nonogram and friends.

Solving Hashiwokakero (Bridges) with Constraint Propagation and a Connectivity Check

SEN LLC — Sun, 12 Jul 2026 23:19:22 +0000

Hashiwokakero (Bridges / 橋をかけろ), the island-and-bridge logic puzzle,
built for the browser with a constraint-propagation solver inside. Three
hinges: (1) the unknowns are exactly one integer per neighbour pair — an
edge carrying 0, 1 or 2 bridges — and each island's clue becomes a
bounds-consistency constraint: an edge must carry at least what its
island's other edges cannot cover, and at most what is left once they take
their minimum. Crossing edges strike each other to zero. Each step is a strict
implication, never a guess. (2) When logic stalls, a backtracking search
branches on the edge with the fewest options, lets propagation prune, and
— crucially — rejects any complete assignment whose bridges leave the islands
in more than one connected component. That connectivity check is what
makes a Hashi solver more than a system of linear equations. (3) Every
bundled board is drawn as its own solved map, so the clues are read off the
answer and can't drift. Solver-equipped puzzle #9.

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

The rules, and the logic that follows

A Hashiwokakero grid is a scattering of islands, each carrying a number. You
draw bridges — straight horizontal or vertical runs over open water — so
that:

Degree — the bridges touching an island total exactly its number.
Capacity — at most two bridges join any one pair of islands.
No crossing — a horizontal and a vertical bridge may never overlap.
Connected — every island ends up in one single group.

The first move is to notice what the unknowns actually are. Two islands are
neighbours when they share a row or column with nothing but water between
them; that gap is the only place a bridge between them can go. So the entire
puzzle is one integer per neighbour pair — an edge carrying 0, 1 or 2
bridges. We track each edge's live range as an interval [lo, hi] ⊆ [0, 2]
and shrink it with two rules that are strict deductions, never guesses.

Degree bounds

An island clued n has some incident edges; their bridge counts must sum to
n. That is a classic sum constraint, and its bounds-consistency form is exact:
each edge must carry at least what the others cannot cover, and at most
what is left once the others take their minimum.

let sumLo = 0, sumHi = 0;
for (const e of inc) { sumLo += lo[e]; sumHi += hi[e]; }
if (need < sumLo || need > sumHi) return { ok: false, forced };  // impossible
for (const e of inc) {
  const wantLo = need - (sumHi - hi[e]);   // others can't cover this — floor
  const wantHi = need - (sumLo - lo[e]);   // others take their min — ceiling
  if (wantLo > lo[e]) raiseLo(e, wantLo);
  if (wantHi < hi[e]) lowerHi(e, wantHi);
}

An island clued 8 with four neighbours forces a double bridge on every side
(sumHi is 8, so every wantLo is 2). A 1 next to a single neighbour whose
edge already carries a bridge is done. Everything in between falls out of the
same two lines.

No crossing

Because a bridge floats over specific cells, a horizontal edge and a vertical
edge can share a cell — and then they cannot both carry a bridge. The moment
one commits to lo ≥ 1, the other's ceiling drops to zero:

for (const [e, f] of g.crossings) {
  if (lo[e] >= 1) lowerHi(f, 0);
  if (lo[f] >= 1) lowerHi(e, 0);
}

Crossings are precomputed once from the geometry: a horizontal edge's floated
cells all sit in one row and a vertical edge's in one column, so any overlap is a
single cell — a fast set test.

propagate() runs both rules to a fixpoint, recording the order edges are
pinned to a single value — which is exactly what the demo's Hint replays,
one guess-free bridge at a time.

When logic stalls: search that proves uniqueness — and connectivity

Plenty of boards need a guess. The backtracking solver branches on the edge
with the fewest options left (a binary hi − lo == 1 choice is ideal), fixes
a value, and lets propagation prune each branch:

function chooseEdge(dom, g) {
  let best = -1, bestSpan = Infinity;
  for (let e = 0; e < g.edges.length; e++) {
    const span = dom.hi[e] - dom.lo[e];
    if (span <= 0) continue;
    if (span < bestSpan) { bestSpan = span; best = e; if (span === 1) break; }
  }
  return best;
}

The subtle part is the acceptance test. Degree bounds are local — they know
nothing about whether the whole map holds together. A board can satisfy every
clue, respect every capacity, cross nothing, and still split into two
island-groups that never touch. Those are not valid Hashi solutions, so the leaf
check runs a tiny union-find over the committed bridges and demands a single
component:

for (let e = 0; e < g.edges.length; e++)
  if (dom.lo[e] >= 1) union(g.edges[e].a, g.edges[e].b);
const root = find(0);
for (let i = 1; i < n; i++) if (find(i) !== root) return false;  // disconnected

Rejecting disconnected leaves is the entire difference between a Hashi solver and
a linear solver. solveAll enumerates up to a limit; hasUniqueSolution stops
at two, and the test suite asserts every bundled puzzle stops at exactly one:

export function hasUniqueSolution(puzzle: Puzzle): boolean {
  return solveAll(puzzle, 2).length === 1;
}

One test makes the point directly: four corner islands each clued 1. Every
degree-valid assignment is two disjoint bridges — top+bottom, or left+right —
never one component. The solver must return no solution, not a disconnected
one, and it does.

Puzzles are solver-verified, not hand-keyed

Every board is authored as the solved map, drawn in ASCII — islands as O,
water as ., and the bridges themselves as the characters that join them:

-  single horizontal      =  double horizontal
|  single vertical        "  double vertical

Here is one bundled board (6×6, 8 islands) as it lives in the source:

O=O--O
|.|.."
|.|.."
O.O-O"
.."..O
..O...

The clue on each island is derived by summing the bridges drawn into it, so
there is no hand-typed number that could drift out of sync with the answer — and
because every cell holds exactly one character, an authored solution can never
contain a crossing. Rule 3 is enforced by the medium itself.

A small growth generator authors them: it grows a connected, crossing-free bridge
structure one island at a time (validity by construction), derives the clues,
then keeps the board only if the solver proves those clues admit a single
solution. The tests re-solve every finished board and assert it recovers exactly
the drawn bridges:

expect(hasUniqueSolution(puzzle)).toBe(true);   // exactly one answer
expect(sol[idx]).toBe(solution.get(key) ?? 0);  // and it's the drawn map

Same discipline as the Kakuro, Nonogram, Slitherlink and Akari entries: ship your
levels through your solver. The six bundled boards run 4×4 (5 islands) up to
10×10 (20 islands).

The UI

The board is one <svg>. Islands are clued discs; each neighbour pair gets an
invisible fat hit-line over the water plus the drawn bridge lines (a double is
two parallel strokes, offset perpendicular to the run). Click cycles an edge
0 → 1 → 2 → 0. A player-facing verdict() mirrors the solver's rules but reports
which things are wrong — islands over their clue, edges that cross — for live
highlighting, and declares a win only when every clue is met, nothing crosses,
and the same union-find shows one connected map.

src/hashi.ts       — pure engine: edge geometry + crossings, bounds-consistency
                     propagation to a fixpoint, union-find connectivity,
                     fewest-options backtracking, uniqueness count
src/hashi.test.ts  — 49 vitest cases
src/puzzles.ts     — 6 ASCII-drawn boards, all generator-made and solver-verified
src/main.ts        — SVG UI: island discs, clickable water, single/double
                     bridges, Hint, animated Solve
tools/generate.mts — growth generator that authors unique boards

No runtime dependencies; TypeScript throughout. MIT-licensed — clone it, read
the engine, lift the bounds-consistency + connectivity pattern.

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

This is part of a series of 100+ small, sharp, open-source builds by
SEN, LLC. Solver-equipped puzzle #9 — after Kakuro, Akari,
Slitherlink, Nonogram, Sokoban and friends.

Solving Kakuro (Cross Sums) with Constraint Propagation — Sum-Combination Domains, Fewest-Candidate Search, and Puzzles Proven Unique

SEN LLC — Sat, 11 Jul 2026 23:30:57 +0000

Kakuro (cross sums / 加算クロス), the addition logic puzzle, built for the
browser with a constraint-propagation solver inside. Three hinges:
(1) every run turns its clue into a domain — of all the ways to pick
k distinct digits that total the clue, the union of every valid
combination is exactly the digits that can appear, so each cell keeps only
what some completion actually uses. Each step is a strict implication, never a
guess. (2) When logic stalls, a backtracking search takes the cell with
the fewest candidates, tries each digit, lets propagation prune, and
proves the answer is unique. (3) Every bundled board is authored as a
filled digit grid — the solver reads the clues off the answer, so picture and
solution can't drift. Solver-equipped puzzle #8.

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

The rules, and the logic that follows

A Kakuro grid is white cells and shaded clue cells. White cells group into
runs — maximal horizontal or vertical strips of two-or-more cells. The
shaded cell left of a horizontal run carries its across sum; the one above a
vertical run carries its down sum. A solution fills every white cell with a
digit 1–9 so that, for every run:

Sum — its digits total the clue.
Distinct — no digit repeats.

Both rules become strict deductions — no guessing:

Sum combinations. For a run that still needs k digits totalling s, enumerate every size-k subset of 1–9 that sums to s. Their union is exactly the digits that can appear, so each open cell keeps only digits some valid completion uses. A pair summing to 3 must be {1,2}; a pair summing to 17 must be {8,9}; a triple summing to 6 must be {1,2,3}.
Distinctness. A digit pinned in one cell is struck from every other cell in the same run.

Digits are bitmasks over 1–9 and a cell's domain is the set still possible
for it. propagate() runs both rules to a fixpoint, recording the order
cells were pinned — exactly what the demo's Hint replays, one guess-free step
at a time.

if (dup || fixedSum > run.sum) return { ok: false, forced };  // run broken
const allowed = comboUnion(pool, remCount, remTarget);        // sum-combo union
if (allowed === 0) return { ok: false, forced };              // no completion
for (const j of open) if (!shrink(j, allowed)) return { ok: false, forced };

comboUnion walks digits in ascending order, so if (d > rem) break prunes the
whole tail the moment the smallest remaining digit overshoots — no wasted
branches.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracking solver takes the cell with the
fewest candidates (minimum-remaining-values), tries each digit, and lets
propagation prune. solveAll enumerates up to a limit; hasUniqueSolution
stops at two, and the test suite asserts every bundled puzzle stops at exactly
one.

export function hasUniqueSolution(puzzle: Puzzle): boolean {
  return solveAll(puzzle, 2).length === 1;
}

Same philosophy as the Sokoban (#286), Nonogram (#287), Slitherlink (#288) and
Akari (#289) entries: ship your levels through your solver.

Puzzles are solver-verified, not hand-keyed

Each board is authored as nothing but a filled digit grid — # and the
digits 1–9. The solver does the rest:

Sum every run of the solution and write that total onto its head as the across/down clue.
Require the resulting clued board to be unique (reject the layout otherwise).

So the answer grid is the single source of truth and the clues are derived from
it — they cannot disagree. The tests re-solve the finished board and assert the
digits match:

expect(hasUniqueSolution(puzzle)).toBe(true);  // exactly one answer
expect(solved[i]).toBe(solution[i]);           // and it's the authored grid

The five bundled boards (5×5 to 8×8, every white cell woven into both an across
and a down run) were found by random-fill search over fixed layouts, kept only
where the derived clues force a single solution.

Takeaway

Kakuro goes a long way on fixpoint propagation of sum-combination domains,
and when that stalls, fewest-candidate search proves the unique answer. That
makes eight solver-equipped puzzles — Sudoku, Lights Out (GF(2)), the 15-puzzle
(parity + IDA*), Sokoban (pull-BFS), Nonogram (constraint propagation),
Slitherlink (edge propagation), Akari (illumination propagation), and Kakuro
(sum-combination domains + a uniqueness proof) — each wearing a different piece
of mathematics. Hit Solve and watch the grid fill in.

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

Solving Akari (Light Up) with Constraint Propagation — Fixpoint Wall/Sight/Illumination Rules, Darkest-Cell Search, and Puzzles Proven Unique

SEN LLC — Fri, 10 Jul 2026 23:22:12 +0000

Akari (Light Up / 美術館), the illumination logic puzzle, built for the
browser with a constraint-propagation solver inside. Three hinges:
(1) three sound rules propagated to a fixpoint — wall counts,
mutual visibility (no bulb may light another), and illumination (a dark cell
whose last possible light source is one candidate forces a bulb). Each is a
strict implication, never a guess. (2) When logic stalls, a backtracking
search takes the darkest cell with the fewest candidates, tries a bulb,
lets propagation prune, and proves the solution is unique. (3) Every
bundled board is authored as a bare wall layout — the solver derives both the
clues and the answer key, so picture and solution can't drift. Solver-equipped
puzzle #7.

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

The rules, and why logic suffices

The grid is white cells and walls (black), some walls numbered 0..4. You drop
light bulbs into white cells. A bulb lights its own cell and shoots a beam
down its row and column that stops at the first wall. A solution must satisfy:

Illumination — every white cell is lit.
No mutual sight — no bulb sits in another bulb's beam.
Wall counts — a numbered wall has exactly that many bulbs adjacent.

Each rule becomes a strict deduction — no guessing:

Wall count — a numbered wall whose adjacent bulbs already equal its number empties its other neighbours; if its remaining free neighbours are exactly what it still needs, they're all bulbs.
Mutual sight — a bulb empties every cell in its beam (and a second bulb in that beam is an immediate contradiction).
Illumination — a still-dark cell whose only remaining light source (itself, or a single unknown in its beam) is one candidate forces a bulb there; zero candidates is a contradiction.

if (bulbs > w.n) return { ok: false, forced };  // wall over-filled
if (count === 0)  return { ok: false, forced };  // a cell can never be lit
if (count === 1)  set(candidate, BULB);          // its last light source

propagate() runs all three to a fixpoint, recording the order cells were
decided — exactly what the demo's Hint replays, one guess-free step at a time.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracking solver takes the darkest cell with
the fewest bulb candidates (minimum-remaining-values on the illumination
constraint), tries a bulb, and lets propagation prune. There's a neat invariant
that makes this tight: after propagation, every lit cell has already been
emptied by the mutual-sight rule, so the remaining unknowns are exactly the
still-dark cells. The search only ever branches where light is genuinely missing.

function chooseCell(state, g) {
  let best = -1, bestCount = Infinity;
  for (const i of g.whites) {
    if (state[i] === BULB || isLit(state, g, i)) continue; // skip already-lit cells
    // count the unknowns that could light i; keep the smallest set
    ...
  }
  return best;
}

hasUniqueSolution enumerates up to two solutions, and the test suite asserts
every bundled puzzle stops at exactly one. Same philosophy as the Sokoban (#286),
Nonogram (#287) and Slitherlink (#288) entries: ship your levels through your
solver.

Puzzles are solver-generated, not hand-keyed

Each board is authored as nothing but a wall layout — # and .. The solver
does the rest:

Solve the bare layout with no clues; illumination + mutual-sight logic alone yields a valid bulb arrangement S.
Number every wall from S, and require the clued board to be unique (reject the layout otherwise).
Greedily blank clues while the solution stays unique, leaving real deductions.

So the picture (the walls) is the single source of truth, and the answer key is
the solver's own output — they cannot disagree. The tests re-solve the finished
board and assert the bulbs match S:

expect(hasUniqueSolution(b.puzzle)).toBe(true);  // exactly one answer
expect(bulbsFound).toEqual(bulbsWant);           // and it's S

The five bundled boards (7×7 to 10×10, all 180°-rotationally symmetric) are
generated this way. The demo's Solve lights the unique arrangement one bulb at
a time, so the dark room fills with light — the header image is the 10×10
"Gallery" the instant it finished.

Takeaway

Akari goes a long way on fixpoint propagation of three sound rules, and when
that stalls, darkest-cell search proves the unique answer. That makes seven
solver-equipped puzzles — Sudoku, Lights Out (GF(2)), the 15-puzzle
(parity + IDA*), Sokoban (pull-BFS), Nonogram (constraint propagation),
Slitherlink (edge propagation), and Akari (illumination propagation + a
uniqueness proof) — each wearing a different piece of mathematics. Hit Solve and
watch the room light up.

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

Solving Slitherlink with Constraint Propagation — Fixpoint Clue/Vertex Rules, Closed-Loop Pruning, and Puzzles Proven Unique

SEN LLC — Fri, 10 Jul 2026 02:27:40 +0000

Slitherlink, the single-loop logic puzzle, built for the browser with a
constraint-propagation solver inside. Three hinges: (1) sound local
rules propagated to a fixpoint — a clued cell that already has enough lines
crosses off the rest, and every lattice vertex must finish with loop degree
0 or 2, which forces or forbids edges. Each is a strict implication, never
a guess. (2) When logic stalls, a backtracking search takes over, pruning
any branch where a stray sub-loop closes (a union-find back-edge), and it
proves the solution is unique. (3) Every bundled puzzle's clues are
derived from a picture (a region mask), and that picture is verified to be the
one and only solution. Solver-equipped puzzle #6.

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

The board is edges, not cells

Slitherlink is an R×C grid of cells, some carrying a clue 0..3. You draw segments
on the lattice edges to make one closed loop; a clue counts how many of its
cell's four edges the loop uses. Each edge is LINE, CROSS, or UNKNOWN. Two
rules make it solvable by pure logic — both strict implications, no guessing:

Clue rule — a clued cell whose lines already equal its number crosses off its remaining edges; if the remainder is exactly what's still needed, they're all lines.
Vertex rule — every lattice vertex must finish with loop degree 0 or 2. Two lines cross off the rest; one line with a single unknown forces that unknown to a line (to reach degree 2); a lone unknown at an empty vertex is crossed (one edge can't reach degree 2).

if (line === 2 && unknown > 0) { /* cross the rest */ }
else if (line === 1 && unknown === 1) { /* that edge is a LINE */ }
else if (line === 0 && unknown === 1) { /* that edge is a CROSS */ }

propagate() runs these to a fixpoint, recording the order edges were
forced. That's exactly what the demo's Hint replays — one guess-free deduction.

When logic stalls: search that proves uniqueness

Sparse boards need a guess. The backtracking solver picks an unknown edge
(preferring one that must continue a half-built path), tries both values, and
lets propagation prune. The big accelerator is premature-loop pruning. Since
every vertex has degree ≤ 2, the drawn segments are always disjoint paths and
cycles — so a union-find back-edge (both endpoints already connected) means a
loop just closed. A closed loop can't grow, so unless it's already the whole
answer, the branch is dead:

if (isSolved(state, g, puzzle)) { solutions.push(crossUnknowns(state)); return; }
if (hasLineCycle(state, g)) return; // a stray sub-loop closed — dead end

hasUniqueSolution enumerates up to two solutions, and the test suite asserts
every bundled puzzle stops at exactly one. Same philosophy as the Sokoban (#286)
and Nonogram (#287) entries: ship your levels through your solver.

Puzzles: the picture is the single source of truth

Each puzzle is authored as a region mask — a simply-connected blob of #
cells. A simply-connected region's boundary is, by construction, one closed loop.
Clues are derived from the mask (an edge is a line iff it separates inside from
outside), so clue and picture can't drift apart. The least-constraining clues
(the 2s) are then blanked greedily, but only while the solution stays unique:

expect(hasUniqueSolution(toPuzzle(def))).toBe(true);  // exactly one answer
expect(foundLines).toEqual(expectedLines);            // and it's the picture

The five bundled puzzles (diamond, plus, heart, S, arrow) are built this way. The
demo's Solve walks the unique loop in order and draws it, so the picture rises
out of the board — the header image is a heart the instant it closed.

Takeaway

Slitherlink goes a long way on fixpoint propagation of sound local rules, and
when that stalls, closed-loop-pruned search proves the unique answer. That
makes six solver-equipped puzzles — Sudoku, Lights Out (GF(2)), the 15-puzzle
(parity + IDA*), Sokoban (pull-BFS), Nonogram (constraint propagation), and
Slitherlink (edge propagation + a uniqueness proof) — each wearing a different
piece of mathematics. Hit Solve and watch a single loop close.

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