Engineering notes

How Sprig makes puzzles with exactly one solution

Luke Lancaster · 27 October 2026

Sprig is a one-star Star Battle game, the same rules as LinkedIn’s Queens. Every board is generated from a text key. Before one ships it must pass two separate tests: an exhaustive search must find exactly one solution, and a deduction solver must finish it using only the logic its difficulty allows.

Here is how that works, with numbers I measured for this page.

The rules as constraints

An N × N board has N coloured regions. Place one Sprig in every row, every column and every region, with no two touching, not even at a corner. Sprig’s boards run from 6 × 6 (Easy) to 10 × 10 (Expert).

One rule shapes the whole search: with one Sprig per row, two Sprigs can only touch across neighbouring rows. Fill the board row by row and the touching rule becomes “this column must be at least two away from the previous row’s column”.

Plant a solution, then grow the regions

The generator starts from the answer. It shuffles a permutation of columns, one per row, until no two consecutive rows have columns within one of each other. Each of those N squares seeds its own region. The regions then grow, one square at a time, into neighbouring unclaimed squares. A region is chosen by integer weights; one of three growth profiles favours small regions, uniform growth or a few long ones. Boards of 8 × 8 and up skip the third profile.

The planted answer is valid by construction. The trouble is that it is almost never the only one. For the first 50 boards of each band in my sample, I counted the solutions of every freshly grown candidate. None of them had exactly one. The median was 15 solutions on 6 × 6, 60 on 7 × 7 and 294 on 8 × 8. On 9 × 9 and 10 × 10 the median reached my counting cap of 1,000.

Counting solutions

The uniqueness check is a plain backtracking search over rows, with columns and regions as bitmasks. A forward check prunes a branch as soon as some unused region has no legal square left in the remaining rows. This is the core of it, from the server’s JavaScript (the app’s Dart is line for line the same):

const feasible = (row, columns, regions, previous) => {
  const free = all & ~columns;
  const nextRow = free & ~(previous < 0 ? 0 : ((7 << previous) >> 1) & all);
  for (let region = 0; region < n; region++) {
    if (regions & (1 << region)) continue;
    let open = byRegion[region * n + row] & nextRow;
    for (let r = row + 1; open === 0 && r < n; r++) open = byRegion[region * n + r] & free;
    if (open === 0) return false;
  }
  return true;
};
const visit = (row, columns, regions, previous) => {
  if (results.length >= limit) return;
  if (row === n) { results.push([...path]); return; }
  if (!feasible(row, columns, regions, previous)) return;
  for (let col = 0; col < n; col++) {
    const cell = row * n + col, region = puzzle.regions[cell];
    if ((columns & (1 << col)) || (regions & (1 << region)) || Math.abs(col - previous) <= 1) continue;
    path[row] = cell;
    visit(row + 1, columns | (1 << col), regions | (1 << region), col);
  }
};
visit(0, 0, 0, -10);

byRegion[region * n + row] is a bitmask of the columns where that region meets that row. The search stops at limit solutions; a proof of uniqueness needs a limit of two. On finished boards it is cheap. Across 200 boards per band, the median proof visited 50 search nodes on 6 × 6 and 1,785 on 10 × 10, with a worst case of 13,201. That typically takes well under a millisecond.

Before the server publishes a ranked board, a second, simpler search in a different module checks it again. That one has no forward check and a budget of one million nodes. The server also re-checks the region shapes and the difficulty grade.

Repairing rival solutions

Rather than throw a candidate away, the generator repairs it. It lists up to 12 solutions, counts how often each square appears in the rivals but not in the planted answer, and moves the most used one into a neighbouring region. The move must leave the old region connected and, where it can, keeps both regions within the band’s size limits.

The move works because every rival using that square already has a Sprig in the destination region. After the move it has two there, so it is no longer a solution. The planted answer never uses the moved square, so it still has one Sprig per region. A move can also create new rivals, so the generator counts again each round. After 3N rounds it gives up on the candidate.

Repair succeeds more often on small boards. Of the fresh candidates above, it produced a unique board for 54% on 6 × 6, 34% on 7 × 7, 15% on 8 × 8, 5.4% on 9 × 9 and 1.8% on 10 × 10. Failures are simply discarded.

Grading by deduction

Exactly one solution doesn’t mean a person can reach it without guessing. So every board is also solved by a deduction engine, which always takes the easiest step available:

1. Tier 1: a row, column or region with one possible square left gets its Sprig.
2. Tier 2: every square that clashes with all of one row’s, column’s or region’s remaining options is crossed out.
3. Tier 3: take two rows, two columns or two regions, each with at most seven options, and list every compatible way to place their two Sprigs. Squares that every arrangement rules out are crossed out, as are squares in those lines that no arrangement uses.
4. Tier 4: the same with three lines.

Every rule is sound: it only places a Sprig that is forced, or crosses out a square that cannot hold one. If the engine finishes the board, that is a second, independent proof that the solution is unique.

Each band has a contract, checked on that easiest-first solve. With the built-in settings, Easy (6 × 6) needs nothing above tier 2 and at most 16 steps. Medium (7 × 7) must need tier 2 at least twice. Tricky (8 × 8) must need at least one tier-3 step, and Hard (9 × 9) at least three, with no tier 4. Expert (10 × 10) must need at least one tier-4 step and at least four steps of tier 3 or above. I can tune these numbers from an admin page; boards already published never change.

Two caveats. Tiers 3 and 4 are bounded case analysis over two or three lines; experienced solvers do this, but it isn’t one glance. And “needs” means this solver’s path needed it; a person may find another route. The step counts are not calibrated against human solving times.

What I could check was that the tiers separate. With its band’s top tier taken away, the solver got stuck on every one of the 200 Tricky, 200 Hard and 200 Expert boards in my sample.

Searching for hard boards

Random growth rarely produces a board that needs tier-3 or tier-4 logic. For every band above Easy, the search keeps the ten hardest near-misses, ranked by their tier counts. A board the band’s tiers can’t finish ranks as “too hard”, which keeps the search near the band’s upper edge. Three times in four, the next candidate is one of those boards with up to five border squares moved to a neighbouring region. The search never moves a planted square and keeps every region connected.

Mutation does most of the work at the top. In my sample it produced 42 of the 200 accepted Medium boards, 87 of the Tricky, 143 of the Hard and 159 of the Expert.

Region shapes are filtered too: a minimum and maximum region size per band, a minimum number of different sizes, and at most one region at the minimum size. That small “anchor” region gives a way in; a hash of the key decides whether a search allows one or none. A search gets 3,000 attempts. If it runs out, it starts again from a new derived key, up to 64 times; it never lowers the bar.

No board in the sample needed a second search, but the slowest Expert board used 2,913 of its 3,000 attempts. The tail is why the server makes boards on worker threads, and an hourly job publishes today’s and tomorrow’s boards before players ask for them.

Starting Sprigs

Some boards open with one Sprig already placed: by default 90% of Easy boards, falling to 30% of Expert. A hash of the key decides whether a board gets one and which solution row it comes from. The board is graded with that Sprig in place, so it counts towards the difficulty. In my sample, 184 of 200 Easy boards and 59 of 200 Expert boards had one.

Same key, same board, two languages

Keys look like dailySet5:2026-10-27:2 or journey:71. The app is Flutter, so it generates in Dart; that is how Journey works offline. The server generates in JavaScript. They must make byte-identical boards. A string hash (FNV-1a) seeds an sfc32 random stream, and everything after it is integer arithmetic. Growth weights are integers, never floats, and every collection is put in a fixed order before the generator picks from it.

// JavaScript: 32-bit wrap-around by hand
const result = (this.a + this.b + this.counter) >>> 0;
this.counter = (this.counter + 1) >>> 0;
this.a = (this.b ^ (this.b >>> 9)) >>> 0;
this.b = (this.c + this.c * 8) >>> 0;
this.c = ((((this.c << 21) | (this.c >>> 11)) >>> 0) + result) >>> 0;

// Dart: 64-bit ints, masked back to 32 bits
final result = (_a + _b + _counter) & 0xffffffff;
_counter = (_counter + 1) & 0xffffffff;
_a = _b ^ (_b >> 9);
_b = (_c + (_c << 3)) & 0xffffffff;
_c = (((_c << 21) | (_c >> 11)) + result) & 0xffffffff;

A 10 × 10 board has 100 squares, more than one 64-bit integer can hold as a bitmask. The Dart grader splits each mask into two words; the JavaScript one uses BigInt. A shared file holds SHA-256 fingerprints of 26 boards across every band. The Dart tests regenerate all 26 and the Node tests a sample covering every band; a mismatch fails the tests. Board IDs carry the generator version, and the app keeps the boards it has saved, so an update never changes a board under a player.

Why the website doesn’t get the generator

The generator is deterministic and league keys are predictable, so a readable copy in the browser would let anyone print future league boards. The website’s puzzles are generated ahead of time under their own keys and shipped as plain JSON. The same code is compiled into the app, so this is friction, not secrecy. Ranked play relies on the server instead. It publishes each board and gives each player one of its eight rotations and reflections, with the colours shuffled. It replays the player’s moves, and a finish faster than anyone could tap the board isn’t ranked. Above that, a speed floor built from the solver’s step counts feeds flags that I review by hand. As a comment in the code says, a legal replay cannot prove a person solved a board unaided.

Easy boards come from a much smaller space than the others, so the server also compares each new Easy board with every one already published. It compares the board’s region borders in all eight orientations, and a board within four border edges of an earlier one is replaced, up to 20 times.

What the hints do

The in-app helper, Wisp, uses its own Dart engine to explain the next step. It tries single squares and familiar patterns first, such as a region confined to one row, then the general two- and three-line search, and finally a contradiction search: “suppose a Sprig here; after a few forced steps, a region has nowhere to go.” The generator never relies on that last kind: every board has already been solved with tiers 1 to 4. One hint checks your crosses against the stored answer and tells you if one covers a square the solution needs. The others work from the board as you see it. The app’s tests follow Wisp from first move to last on sample boards in every band, checking that each Sprig it places is in the solution and each cross it marks is not.

If you want to try one, today’s daily puzzle is free in the browser, and the app is on the home page.