DEV Community

SEN LLC
SEN LLC

Posted on

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

#typescript #algorithms #constraintsolving #gamedev

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

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

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

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

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

Top comments (0)