Connections puzzle engine

1. Foundational mental model

Connections (/challenges/connections) shows 16 flags. The player selects four that share a theme and submits. Each board has exactly four groups, one per tier: yellow, green, blue and purple, from most to least obvious.

The board is generated in the browser by generateConnectionsPuzzle({ mode }). It fills the tiers in order with a depth-first search, backtrackCategories. At each tier it shuffles every candidate category for that tier, tries them one at a time, and recurses. A candidate fails when too few of its countries are still free. When a deeper tier runs out of candidates, the search pops the last category and tries the next candidate at the tier above.

A candidate is either a library category (a hand-written label with a country list) or a synthetic category built from a flag tag such as hasCanton or colors:…. Placing a category does two things to shared state:

• The four chosen countries go into usedCodes.
• Every other country in the category’s pool (the spill) goes into forbiddenCodes, so later groups cannot use a tile that would also fit this label.

One level of backtrackCategories: try each shuffled move, recurse, undo on failure.

After a full board is found, DECOY_CHANCE (0.25) of boards get one tile swapped for another member of the same group’s pool. The 16 codes are shuffled and the answer pools are stripped before the board reaches the UI.

The simulator below runs the same generator with a seeded random source and records each step. Pick a seed, then step through or play it. Seed 12 in flags mode fails ten blue candidates, backtracks to green, and then finds a board.

Interactive

Connections board search

Runs a mirror of the production generator (parity-tested against connections-logic.ts) with a seeded random source. Step through the backtracking search that picks one group per tier.

Seed New seed

Pool

Flags only + trivia

Step Play Reset Finish

Speed

SlowNormalFast

Attempts

0

Backtracks

0

Depth

0/4

Step

0/182

Ready. Press Step or Play to walk through the search.

Search stack (one group per tier)

1. Yellow searching
2. Green empty
3. Blue empty
4. Purple empty

Current candidate

No candidate under test.

Already on the board Forbidden spill from an earlier group

2. Implementation status & known gaps

Connections is live with two modes. Flags only uses visual flag tags. + trivia (the “Include geography and trivia” checkbox, stored in localStorage under flags.connections.puzzleMode) adds geography and trivia categories. PRE_PACKAGED_PUZZLES and getPrePackagedPuzzle exist in connections-logic.ts, but nothing calls them. Every board is generated.

Active invariants & limitations

• Four tiers, four tiles each: ITEMS_PER_CATEGORY is 4 and the board has 16 codes.
• No two groups share a code. checkGuess depends on this.
• MAX_MISTAKES is 4. A one_away result counts as a mistake and shows a “One away” toast.
• Resubmitting a set that already failed is blocked without costing a mistake (“Already tried this group”).
• The player wins when all four groups are solved with fewer than four mistakes.
• The search is incomplete. Each move draws one random 4-subset and never tries a second subset of the same category.
• forbiddenCodes is a plain Set, so a backtrack can remove a code that an earlier category still needs forbidden (section 5).
• The web app uses Math.random through shuffleArray, so a board cannot be reproduced from a seed in production.

3. Concrete implementation

Candidate moves for a tier

Library categories need at least four unique codes. Synthetic tags already used on this board are excluded. Both kinds go into one list, shuffled once per call:

apps/web/src/routes/challenges/connections/connections-logic.ts

  const syntheticTagsForTier = syn.byTier[tier].filter((t) => !usedSyntheticTags.has(t));

  const moves: CandidateMove[] = [
    ...libraryMatches.map((category) => ({ kind: "library" as const, category })),
    ...syntheticTagsForTier.map((tag) => ({ kind: "synthetic" as const, tag })),
  ];
  const shuffledMoves = shuffleArray(moves);

Placing and undoing a library move

apps/web/src/routes/challenges/connections/connections-logic.ts

      chosen.push(resolved);
      for (const code of chosenFour) {
        usedCodes.add(code);
      }
      for (const code of spill) {
        forbiddenCodes.add(code);
      }

      if (
        backtrackCategories(
          mode,
          library,
          tierIndex + 1,
          tiers,
          chosen,
          usedCodes,
          forbiddenCodes,
          usedSyntheticTags
        )
      ) {
        return true;
      }

      chosen.pop();
      for (const code of spill) {
        forbiddenCodes.delete(code);
      }

Extra checks on synthetic moves

buildSyntheticCategory rejects a tag when its tier does not match, when any tile already on the board carries the tag (usedCodesHaveConnectionsTag), or when fewer than four of its countries are free:

apps/web/src/routes/challenges/connections/connections-logic.ts

  if (usedCodesHaveConnectionsTag(usedCodes, tag, includeGeo)) {
    return null;
  }

  const available = countries.filter(
    (code) => !(usedCodes.has(code) || forbiddenCodes.has(code))
  );
  if (available.length < ITEMS_PER_CATEGORY) {
    return null;
  }

The tag-on-board check looks backward, at tiles already placed. Library moves have no equivalent, so an earlier tile can belong to a later library category’s pool.

The decoy

tryApplyDecoy picks a group whose pool is larger than four, drops one of its tiles at random, and adds the first pool member not already on the board:

apps/web/src/routes/challenges/connections/connections-logic.ts

  for (const cat of shuffled) {
    const pool = cat.answerPool ?? [];
    const herrings = pool.filter((code) => !cat.countryCodes.includes(code));
    const decoy = herrings.find((code) => !usedCodes.has(code));
    if (!decoy) {
      continue;
    }

The decoy is still a real member of its group’s label. It checks usedCodes only, so it can pick a code that forbiddenCodes was keeping off the board, which means it may also fit another group.

Grading a guess

apps/web/src/routes/challenges/connections/connections-logic.ts

  for (const category of categories) {
    const categorySet = new Set(category.countryCodes);
    const intersection = selectedCodes.filter((code) => categorySet.has(code));

    if (intersection.length === ITEMS_PER_CATEGORY) {
      return { result: "correct", matchedCategory: category };
    }
    if (intersection.length === ITEMS_PER_CATEGORY - 1) {
      return { result: "one_away", matchedCategory: null };
    }
  }

Because groups are disjoint, at most one group can hold three or more of the four selected tiles, so the loop order never changes the answer.

A guess in ConnectionsChallenge.svelte.

The docs mirror

The simulator cannot import apps/web, so apps/docs/src/lib/connections-board-generator.ts copies the generator with two additions: an injected random function and an onEvent callback. connections-board-generator.test.ts runs the web original with Math.random replaced by the same seeded generator and asserts identical boards for 300 seeds in each mode, and identical checkGuess results.

4. Internal mechanics & mathematics

Branching factor

Let $m_d$ be the number of candidate moves at depth $d$ (tier $d$). The recursion tree has at most

$$L \le \prod_{d=0}^{3} m_d$$

leaves. From the current library and synthetic tag tables:

Mode	$m_0$ yellow	$m_1$ green	$m_2$ blue	$m_3$ purple	$\prod m_d$
Flags only	15	13	27	3	15,795
+ trivia	20	53	33	9	314,820

The flags-only library has no purple categories, so purple has only three synthetic tags. Each of them covers 14 countries.

Why the search is incomplete

A move commits to one random 4-subset $S$ of its free codes. For a pool of $n$ free codes there are $\binom{n}{4}$ possible subsets, for example $\binom{107}{4} = 5{,}160{,}610$ for the horizontal-stripes pool. If a deeper tier fails, the search moves on to the next category and never tries another $S$. The generator can therefore report failure on a tier assignment that has a solution under a different subset. In practice the top-level call has not been observed to exhaust: every seed tested returned a board.

Measured cost

Over 2,000 seeds with the instrumented mirror:

Metric	Flags only	+ trivia
Mean moves tried	50.5	6.5
Median / p90 / p99	6 / 69 / 818	6 / 9 / 18
Max moves tried	1,482	143
Boards with no backtrack	1,397 of 2,000	1,970 of 2,000
Decoy applied	486 of 2,000 (24.3%)	568 of 2,000 (28.4%)

In flags mode the purple tier dominates. It was entered 20,523 times and exhausted 18,523 times, a success rate near 9.7% per entry. The main reason is the synthetic tag-on-board check: skip reasons were tag_on_board 70,437 times, too_few_pickable 1,424 and too_few_available 1,315.

A naive estimate treats each of the 12 placed tiles as carrying a 14-country tag independently, with probability $14/205$:

$$P(\text{no placed tile has the tag}) \approx \left(1 - \frac{14}{205}\right)^{12} \approx 0.43$$

That overestimates success. Shields, emblems and text cluster on the same flags, and the earlier tiers often place one of them.

5. Threat model, failure modes & edge cases

Connections has no server component and awards nothing that needs verification beyond completeChallenge. The failure modes are about puzzle quality.

Ambiguous tiles

A board is ambiguous when a tile outside a group is in that group’s source pool, so the tile honestly fits two labels. Measured over 5,000 seeds:

Path	Flags only	+ trivia
All boards	527 (10.5%)	579 (11.6%)
No backtrack, no decoy	0 of 2,593	285 of 3,652
Backtrack, no decoy	231 of 1,124	not broken out
Decoy, no backtrack	174 of 893	not broken out
Backtrack and decoy	122 of 390	not broken out

Three separate causes produce these:

1. Spill is not reference-counted. Two categories can both spill the same code. When the later one is undone, forbiddenCodes.delete(code) removes it even though the earlier category still needs it forbidden. With seed 12 in flags mode, yellow “Flag has horizontal stripes” forbids ET. At the blue tier, the synthetic “Flags with green, yellow and red” also spills ET and is later undone, which deletes ET. The search then backtracks to green and places “pan-African colors” as GN, ET, GH, CM. On the final board ET, GH, BG and HR all fit the yellow label too.
2. Library pools are checked in one direction only. Later groups cannot pick codes in an earlier pool, but an earlier tile can sit in a later library category’s pool. This is the source of the 285 direct boards in + trivia mode.
3. The decoy ignores forbiddenCodes.

Seed 12, flags mode: an undo deletes a code that yellow still forbids.

Grading is unaffected: checkGuess compares against the generated groups only. A player who picks a tile that fits the label but belongs elsewhere gets one_away or wrong.

Other edge cases

• Exhaustion. If the top level returns false, generateConnectionsPuzzle throws “Connections: no valid category combination found”. No seed tested hit it.
• Retry cost. The p99 of 818 moves in flags mode is still fast, but the tail is long. The slowest seed tried 1,482 moves.
• Purple is thin in flags mode. With three tags, a player who knows them can often guess purple first.

6. Architectural tradeoffs & non-goals

Decision	Benefit	Cost
Generate every board in the browser	Unlimited boards, no backend	No seed, so no shared or replayable board. No server check of quality.
Randomised DFS, one subset per move	Simple code, fast on average	Incomplete search. Long tail in flags mode.
Spill into a flat Set	Cheap add and delete	Undo can clear a code another group still forbids.
Synthetic tags from flag data	Categories stay in sync with country attributes	Purple in flags mode has only three options.
25% decoy	Adds a harder tile to some boards	Can create a tile that fits two groups.
Disjoint groups	Order-independent grading	Needs the forbidden-set logic to hold for the board to feel fair.

Non-goals: daily or shared Connections boards (the pre-packaged path is unused), difficulty tuning per player, and server-side generation.