DEV Community

SEN LLC
SEN LLC

Posted on

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

#typescript #algorithms #constraintsolving #gamedev

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

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:

  1. Illumination — every white cell is lit.
  2. No mutual sight — no bulb sits in another bulb's beam.
  3. 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
Enter fullscreen mode Exit fullscreen mode

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;
}
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),
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:

  1. Solve the bare layout with no clues; illumination + mutual-sight logic alone yields a valid bulb arrangement S.
  2. Number every wall from S, and require the clued board to be unique (reject the layout otherwise).
  3. 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
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)