DEV Community

SEN LLC
SEN LLC

Posted on

Solving Star Battle with Constraint Propagation and a Uniqueness Proof

#typescript #algorithms #constraintsolving #gamedev

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

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:

  1. Rows — every row holds exactly k stars (k is 1 or 2).
  2. Columns — every column holds exactly k stars.
  3. Regions — every region holds exactly k stars.
  4. 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);
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

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

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

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.

Top comments (0)