From 4.5 Seconds to 6 Milliseconds: What Actually Made Our Star Battle Solver ~700 Faster

Every puzzle site that offers a "solve this board for me" button eventually faces the same awkward demo: paste in a hard 10×10 Two Not Touch board, press solve, and watch the spinner.

Ours doesn't spin anymore. On the site's actual daily puzzle archive — thirty real 10×10 boards — the solver finds and uniqueness-verifies every solution in ~6 ms at the median, with the slowest board at 53 ms. The naive version we kept around for comparison, running on the same boards with the same semantics, takes ~4.5 seconds. That's roughly a 700× gap, and none of it came from micro-tuning.

This post is the story of where the 700× actually came from. Short version: change the representation of the search, and the loop optimizations become optional.

(If you read the first post about our zero-guess generator, the machinery will look familiar — this one is the solver-side sequel: how fast the engine runs, measured, and why a 6 ms solver unlocks interaction designs a multi-second one makes impossible.)

If you want to follow along on a real board, the interactive solver is free to use — paste any grid, including from other sites, and watch it reason.

The rules, briefly

An N×N grid split into N regions. Place K stars in every row, every column, and every region (K=1 on 8×8, K=2 on 10×10). No two stars may touch — not even diagonally.

The no-touch rule is the villain of this piece. It's what couples adjacent rows together and what makes the search space explode if you represent the problem carelessly.

The baseline: place stars one cell at a time

The first working version did the obvious thing: iterate cells in reading order, try placing a star, check every constraint against all placed stars, recurse. Classic backtracking, straight out of a textbook, with a maxSolutions = 2 cap so every solve doubles as a uniqueness proof (find one solution, then prove there's no second — more on why that matters in the generator post).

We benchmarked that version for this post, on the production puzzle archive: ~4.1–4.5 seconds per 10×10 board, median 4.47 s. Why so slow? Three compounding reasons:

1. The branching factor is huge. Every empty cell is a binary choice, and constraints only prune after you've committed to a placement.
2. Every check is O(placed stars). Column counts, region counts, the touch rule — all re-scanned against everything placed so far.
3. The search re-derives the same row-level structure millions of times. Star Battle's constraints are almost entirely row-aligned; a cell-level search never gets to exploit that — it rediscovers it one cell at a time.

Profiling pointed squarely at the checking and the recursion overhead around it. The lesson of stage 1 writes itself: if the profile points at the checking, the fix usually isn't a faster check — it's a representation where checking becomes unnecessary.

Stage 1 (~100×): enumerate row placements, not cells

Within any single row, the no-touch rule means valid star layouts form a small closed set: all K-subsets of columns with no two adjacent. Precompute them once:

function rowCombos(N: number, K: number): number[][] {
  const out: number[][] = [];
  const gen = (start: number, depth: number, cur: number[]) => {
    if (depth === K) { out.push([...cur]); return; }
    for (let c = start; c < N; c++) {
      if (depth > 0 && c <= cur[depth - 1] + 1) continue; // no touching in-row
      cur.push(c); gen(c + 2, depth + 1, cur); cur.pop();
    }
  };
  gen(0, 0, []);
  return out;
}

For 10×10 with K=2 that's 36 valid row layouts instead of C(10,2) = 45 placements — and for 8×8 with K=1, just 8. The search is now over rows: at each row, try each compatible layout and advance.

In-row touching is guaranteed by construction, so an entire class of checks vanished from the hot path. This single change — collapsing "binary choices over 100 cells" into "sequences of 36 layouts over 10 rows" — was worth roughly two orders of magnitude on its own.

Stage 2: pigeonhole bounds, made O(1) with suffix sums

Next, ask a feasibility question before recursing: with the rows still unexplored, can every column and every region still reach its quota of K?

const remRows = N - row;
// Can every column still get its remaining stars?
for (let c = 0; c < N; c++) {
  if (colCounts[c] + remRows < K) return; // dead branch
}
// Can every region still get its remaining stars?
// remRegionCells[r][g] = how many cells of region g are in rows r..N-1 (precomputed)
for (let reg = 0; reg < N; reg++) {
  if (regCounts[reg] + remRegionCells[row][reg] < K) return;
}

remRegionCells is a suffix-sum table built once per solve in O(N²) — for each row index, how many cells of each region remain at or below it. With it, both feasibility checks are flat scans with no board traversal.

The column check catches the obvious dead ends ("column 3 still needs 2 stars but we're on the last row"). The region check is subtler and deadlier: regions are irregular blobs, and it's common for a region's remaining cells to sit in rows the search is about to leave behind. Killing those branches before they spawn children is where a large part of the remaining speedup lived.

Stage 3: exploit row locality, not bit tricks

The last change wasn't an algorithm swap — it was shrinking the per-candidate checks by exploiting where stars can actually be:

• The touch check only needs the previous row. Stars in the same row are impossible by construction, and rows further back can't touch row r. So the diagonal check is an O(K) scan of the previous row's stars — not a pass over all placed stars:

  for (let i = stars.length - 1; i >= 0 && stars[i][0] === row - 1; i--) {
    if (Math.abs(stars[i][1] - c) <= 1) { ok = false; break; }
  }

• Region capacity as a per-row delta. Instead of recounting regions, each candidate row layout contributes a tiny regAdd map (which regions this row's stars land in, and how many); the feasibility test is regCounts[reg] + regAdd[reg] <= K for at most K keys.

Neither change is glamorous. Together they turn the per-layout compatibility test into a handful of O(K) operations — and, more importantly, they stop the hot path from touching big shared state, which keeps the JIT happy and the recursion lean.

Worth noting what we didn't do: no bitmasks, no WASM, no workers. After stages 1–2 the search tree is already so small that state representation stopped being the bottleneck — there was nothing left for bit-packing to buy. That's the honest other half of the micro-optimization lesson: once the tree is small, leave the state alone.

Where it landed — measured

On the production daily archive (30 real 10×10 boards, every solve including the two-solution uniqueness verification):

Solver	Median	Slowest board
Naive cell-by-cell	4,470 ms	4,521 ms
Production engine	6.0 ms	52.7 ms

The whole archive — a month of dailies — verifies in 307 ms total. One board out of the thirty took ~53 ms; that's the long tail of adversarial region layouts, and it's still three orders of magnitude ahead of the baseline.

But raw speed turned out to be the smaller payoff. A single-digit-millisecond solver unlocks interaction designs a multi-second one makes impossible:

• Instant feedback on pasted boards — including boards from newspapers or other sites, which is how a meaningful chunk of players actually use the solver page.
• A hint engine that never batches or debounces — the UI can ask "is this candidate still consistent with some solution?" on every click and answer within a frame budget.
• Batch validation in CI — the generator's uniqueness oracle runs the same code, and the month's daily boards verify in about a third of a second on a GitHub runner.

The general sequence, for anyone optimizing their own constraint search:

1. Profile first — it will point at the constraint checker, and the fix is almost never a faster checker.
2. Change the granularity of the search (cells → rows) before touching anything else. Representation beats tuning, every time.
3. Add feasibility bounds (pigeonhole + suffix sums) to kill dead branches early — this is where irregular structure (regions) stops being free.
4. Then shrink the per-candidate checks by exploiting the structure you've exposed (row locality, per-row deltas). And when the profile goes quiet, stop — the tree was already small enough that nothing else mattered.

The full engine is ~300 lines of dependency-free TypeScript. If you're curious how it behaves on your favorite daily puzzle — including the ones it has no business solving instantly — paste it in here. And for the rules walkthrough of the Two Not Touch variant, start here.

Happy puzzling — and may your branches die young.