How I Generate Word-Connection Puzzles in Milliseconds

A technical report: From sluggish Go services and solver dead ends to a hand-written generator

For my browser game Stränge (along with its Swedish edition Strängar and Spanish version Hebras), I need new word-connection puzzles every single day. The core concept is simple: a grid full of letters, a theme, and players connect adjacent cells to uncover all the hidden words. While it looks like a casual pastime on the surface, under the hood it turns out to be a surprisingly tough combinatorial problem.

Without an entire editorial team to lean on, crafting these puzzles completely by hand takes far too much effort. That’s why I relied on a generator right from the start to automate at least part of the heavy lifting. This allowed me to focus on content curation while the algorithm figured out a valid placement for the words on the board.

In my paper “Generating Word-Connection Puzzles: An Experience Report”, I documented the underlying math and empirical benchmarks. Here, I want to share the journey, the dead ends, and the core concept in plain English—without getting lost in heavy formulas and pseudocode.

The Game Rules: What the Generator Actually Needs to Solve

The board consists of an 8×6 grid. Movement is allowed horizontally, vertically, or diagonally (known in graph theory as a King’s Graph). A valid puzzle must satisfy five constraints:

1. Complete Coverage (C1): All 48 cells must be covered by paths—no cell can be left empty, and none can be visited more than once.
2. Word Pool & Uniqueness (C2): Each path must spell out a distinct word from the predefined thematic pool.
3. Clean Visuals (C3): Crossing diagonals within any 2×2 block are forbidden because they look like rendering bugs or visual glitches.
4. Local Uniqueness (C4): By far the nastiest constraint! No placed word may be traceable anywhere else on the board. If a word can be traced twice, the puzzle breaks. As a player, you definitely don't want to find a bonus word for hints that also happens to be a hidden solution elsewhere—or worse, trace a word using a slightly different path that gets rejected simply because you ended on the wrong "E". This uniqueness check is the primary bottleneck of the generator, as it evaluates the entire geometry and word assignment simultaneously.
5. The Spanning Word (C5): A central theme word must span from one edge of the board completely to the opposite edge.

Where I Started: A Sluggish Go Service and a Sneaky Bug

My first working generator ran as a Go microservice consuming puzzle generation jobs from a Redis queue. The approach was pragmatic, but naive: it attempted to construct the geometry and assign the words at the same time within a single recursive search.

The catch: the uniqueness check (C4) was only executed at the very end on the fully populated board. If the board turned out to be ambiguous, the entire attempt was discarded, and the search started over from scratch. Because almost every random letter assignment introduces ambiguities, the service frequently got trapped in endless restart loops.

Still, this approach managed to generate the vast majority of puzzles to date—albeit at the cost of substantial CPU time. A TypeScript port was even deployed to the browser so players could create their own custom puzzles, but the performance was dismal.

The Hidden Bug in the Go Validator: While auditing the legacy logic, I discovered a bug that made the old validation far too strict, rejecting 12 out of 25 perfectly valid puzzles.

The Dead End: Constraint Programming with CP-SAT

My initial idea for the rewrite: let an industrial-grade solver handle it! I built a monolithic constraint model using Google's CP-SAT. Spoiler: it didn't work at all.

C4 simply didn't map cleanly into the model: every failed state was a tiny "near miss" (e.g., an adjacent cell that happened to share a letter, enabling a shortcut). Incrementally blocking these alternative paths using lazy constraints failed to converge—after 6 iterations and 60 seconds of compute time, the board was still littered with ambiguities.

The Breakthrough: Two-Stage Decomposition

The breakthrough came when I took a closer look at the actual nature of constraint C4:

C4 depends almost entirely on the word assignment—not on the underlying geometry. If you swap the words on an existing path layout, every letter changes, reshaping the entire landscape of potential ambiguities. Conversely, tweaking the geometry while keeping the same words rarely helps.

This realization led to a clean, two-stage pipeline:

• Stage 1 (Geometry): Partition the 48-cell grid into paths of the required lengths. Which words end up on those paths doesn't matter yet—this stage is purely about lengths and satisfying C1, C3, and C5.
• Stage 2 (Word Assignment): Given a valid geometry, use backtracking to assign matching words, verifying C4 incrementally.

The speedup in Stage 2 is enormous: evaluating an assignment takes mere microseconds. Once a letter is set, it stays fixed. If the checker spots a conflict on a partially filled board, the algorithm prunes the entire subtree immediately.

Pushing Further: Ditching the Solver for a Hand-Rolled Generator

With Stage 1 freed from handling words, the geometry problem became far smaller than anticipated. Instead of pulling in the heavyweight CP-SAT solver, I wrote a dedicated, randomized depth-first search:

• Place the spanning word first, since it has to cross the entire board.
• Start each subsequent path at the cell with the fewest free neighbors (the one most vulnerable to getting isolated).
• After each placement, run a lightweight dynamic pre-filter (subset-sum) to verify whether the remaining connected components can still be partitioned into the available word lengths. Dead ends are detected instantly.

Benchmark results (Apple M4 Pro):

The hand-rolled algorithm outperforms the solver approach by a factor of 569× at the median—primarily because the model initialization and presolve overhead in a general-purpose solver is sheer overkill for a problem of this scale.

Browser support via WebAssembly

A welcome side effect of dropping OR-Tools: shedding over 50 MB of native C++ dependencies. The new codebase is pure managed C# (.NET) and compiles directly to WebAssembly.

This brings fast puzzle generation straight into the browser. Supporters of the game can now build their own puzzles in an instant, without their devices heating up or spinning up fans. An update featuring the new generator is rolling out shortly.

Takeaways

Sometimes the best optimization isn't reaching for a faster solver, but taking a step back: by analyzing the structure of the problem and decoupling geometry from content, a brutal combinatorial grind turns into a task solved in fractions of a millisecond.

If you're interested in the formal definitions and pseudocode, all the details are available in the full paper.