DEV Community

SEN LLC
SEN LLC

Posted on

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

#typescript #algorithms #constraintsolving #gamedev

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

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:

  1. Degree — the bridges touching an island total exactly its number.
  2. Capacity — at most two bridges join any one pair of islands.
  3. No crossing — a horizontal and a vertical bridge may never overlap.
  4. 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);
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

O=O--O
|.|.."
|.|.."
O.O-O"
.."..O
..O...
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)