Designing a Zero-Guess Puzzle Generator for Star Battle (Two Not Touch) Using Constraint Logic

If you have ever played Star Battle (sold as Two Not Touch in some newspapers, and recently popularized again by LinkedIn's Queens), you know the genre's dirty secret: a lot of online generators produce puzzles that force you to guess.

You reach a board state where three cells could plausibly hold a star, the grid gives you no way to eliminate any of them, and the only path forward is bifurcation — pick one, play ten moves, hit a contradiction, unwind, try the next. That's not deduction. That's search with extra steps. Some generators don't even verify uniqueness, so your "wrong" branch may actually be a second valid solution.

A pencil puzzle should be solvable with logic alone. When I built Star Battle Online, I made one rule non-negotiable: every published puzzle must be machine-verified to have exactly one solution, and (for our graded levels) be reachable through human deduction rules without branching. This post walks through the constraint engine that makes that cheap — it verifies a 10×10, 2-star board in ~10–15 ms of pure TypeScript, no WASM, no workers.

The rules, as constraints

Quick refresher. An N×N grid is partitioned into N regions. Place K stars per row, per column, and per region (K=1 for 8×8, K=2 for 10×10 in the classic format), with the twist that no two stars may touch, not even diagonally.

As a constraint system that's:

• rowCount[r] == K for all rows
• colCount[c] == K for all columns
• regionCount[g] == K for all regions
• for any two stars at (r1,c1), (r2,c2): max(|r1-r2|, |c1-c2|) > 1

The last one is what makes the search space interesting. It couples adjacent rows: a star in row r eliminates up to three cells in row r+1.

Step 1: Precompute row placements, don't enumerate cells

The naive solver places stars cell by cell. That's wasteful, because the no-touch rule within a row reduces each row to a small, closed set of possibilities: all K-subsets of columns where no two chosen columns are adjacent.

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

For a 10×10 grid with 2 stars that's 36 combinations instead of C(10,2) = 45 — and for the search below, we never think in individual cells again. The whole solver is a backtracking over rows, trying precomputed combinations against running column/region tallies.

Step 2: Pigeonhole pruning with suffix sums

The two pruning rules that do almost all of the work:

// Pigeonhole check 1: can every column still reach K?
for (let c = 0; c < N; c++) {
  if (colCounts[c] + remRows < K) return;
}
// Pigeonhole check 2: can every region still reach K?
for (let reg = 0; reg < N; reg++) {
  if (regCounts[reg] + remRegionCells[row][reg] < K) return;
}

If a column needs 2 more stars but only 3 rows remain, fine. If it needs 2 and 1 row remains, the branch is dead — kill it before recursing. Same for regions, using remRegionCells[r][g]: a suffix-sum table of how many cells of region g live in rows r..N-1, precomputed once per solve in O(N²).

This is textbook pigeonhole bounding, and it's the difference between a search that explodes on adversarial grids and one that finishes in milliseconds. The diagonal-touch check only needs to look at the previous row (stars are never in the same row twice apart, and rows further back can't touch), so it's an O(K) comparison against the last placed row — not a scan of all placed stars.

Step 3: Uniqueness is a stopping condition, not a post-check

Here's the part most hobby generators get wrong. They find a solution and ship the puzzle. To guarantee uniqueness you keep searching past the first solution:

solve(regions: number[][], maxSolutions = 2): [number, number][][] {
  // ...backtracking as above, but:
  if (row === N) {
    if (regCounts.every((cnt) => cnt === K)) {
      solutions.push(...);
      if (solutions.length >= maxSolutions) return; // early exit
    }
  }
}

Asking for up to 2 solutions turns the solver into an oracle: solutions.length === 1 means the board is strictly unique. The early exit means proving uniqueness usually costs barely more than solving once, because a second solution, when it exists, tends to be found nearby in the tree.

Step 4: Generating regions that look organic

Solving is half the problem — the other half is producing region partitions that look hand-drawn instead of like output of a grid splitter. Our pipeline:

1. Sample a valid star layout first (rows × precomputed combos, columns filled to K, ignoring regions), using shuffled combination order for variety.
2. Seed a Voronoi partition from those stars: for K=2 we shuffle the star list, group stars into N chunks, and use each chunk's centroid as a seed. Every cell joins its nearest seed.
3. Reject non-contiguous partitions. Voronoi cells under Euclidean distance are usually connected, but not always — a BFS per region (allConnected) filters those out, because classic Star Battle regions must be orthogonally connected.
4. Run the uniqueness oracle. solve(regions, 2) — if it returns exactly one solution, ship it; otherwise resample. The whole loop retries up to 30 times per board size, and in practice a strictly unique board appears within the first handful of samples.

The beautiful side effect of seeding Voronoi from the solution itself: regions stay "fair" — each region contains roughly the mass it needs for its K stars — which biases the generator toward puzzles that are dense in constraint interactions rather than degenerate ones.

Why "zero guess" is a feature, not a slogan

None of this would matter if players couldn't tell. But they can. The recurring complaint about generated Star Battle variants (check any puzzle subreddit) is exactly the bifurcation problem: boards where deduction dries up and guessing takes over, or boards with multiple solutions where the "check" button flags a valid layout as wrong.

So the guarantee we ship on the tin — computer-verified unique solution, solvable by pure logic — is enforced at generation time by the engine above, not asserted by hope. If you want to feel the difference, the daily boards and the full rules walkthrough for the Two Not Touch variant are free to play here, and there's an interactive step-by-step solver where you can paste any grid and watch the constraint engine reason — including boards from other sites, if you want to check their uniqueness claims.

Takeaways

• Enumerate row placements, not cells. Collapsing a row into precomputed non-touching K-subsets shrinks the branching factor dramatically and makes adjacency checks trivial.
• Prune with pigeonhole bounds, made O(1) with suffix sums. Column and region feasibility checks kill dead branches before they spawn children.
• Make uniqueness a search bound (maxSolutions=2), not a post-hoc loop. The early exit makes strict-uniqueness verification nearly free.
• Generate geometry from the solution. Voronoi-from-stars gives organic, connected, "fair" regions without any hand-tuned heuristics.

The entire engine is ~300 lines of dependency-free TypeScript, runs the uniqueness check in ~10–15 ms for 10×10, and comfortably generates a month of daily puzzles in under a second — small enough to embed, audit, or port. Happy puzzling.

Comments

[Raknaos]

maxSolutions=2 as a stopping condition is the best trick in puzzle generation and still badly underused — most solvers I've read find one grid, declare victory, and ship boards with three solutions. Bounding the search is strictly cheaper than enumerating it, and your observation that the second solution sits near the first in the tree matches mine: proving uniqueness costs almost nothing extra, while proving non-uniqueness is the expensive case.

Since you went from generator to a daily calendar, how do you rate difficulty? A board can be strictly unique and still need a colouring chain nobody spots at a cafe table. Did you end up with a solver-side proxy — forced-move depth, how long the candidate lists stay narrow before a breakthrough — or does the rating just come from watching people chew on it?