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: The branching factor is huge. Every empty cell is a binary choice, and constraints only prune after you've committed to a placement. Every check is O(placed stars). Column counts, region counts, the touch rule — all re-scanned against everything placed so far. 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 c…