Puzzle transposition engine

Status: Production
Source: 7 files · web 6 · shared 1
web
routes/challenges/puzzle/PuzzleChallenge.svelte
routes/challenges/puzzle/puzzle-utils/constants.ts
routes/challenges/puzzle/puzzle-utils/board.ts
routes/challenges/puzzle/puzzle-utils/initial-board.ts
routes/challenges/puzzle/puzzle-utils/signatures.ts
routes/challenges/puzzle/puzzle-utils/initial-board.test.ts
shared
game-logic/game-logic.ts
Verified: 2026-09-27 against master

1. Foundational mental model

The Puzzle challenge (/challenges/puzzle) cuts a flag into a grid, scrambles the tiles, and asks the player to rebuild it. A move picks any two tiles and swaps them: tap one then another, or drag one onto another. Tiles never slide, and there is no blank cell.

The board is an array tilesBySlot, where tilesBySlot[slot] is the index of the piece shown in that slot. Piece $i$ belongs in slot $i$ . Mathematically the board is a permutation $\pi$ of $\{0, \ldots, n-1\}$ , a swap is a transposition, and the result screen compares the player’s swap count with the fewest transpositions that would have solved the starting board.

Game start: sample tile colors, shuffle until the board is not already solved, then compute the par.

Many flags have tiles that look the same: the top and bottom tile of each stripe in a vertical tricolor, most of Japan’s white field. The engine treats those tiles as interchangeable. It fingerprints each tile’s pixels, calls the puzzle solved when every slot shows a tile that looks right, and computes par against the best of all visually solved layouts.

2. Implementation status & known gaps

Active today: three grids, all using DIFFICULTY_SETTINGS in constants.ts: Easy 3×2 (6 tiles), Medium 4×3 (12), Hard 5×3 (15). The internal keys are regular, pro, elite.
Active today: the starting board is never the identity and never visually solved (initial-board.test.ts checks this across all grids and several signature patterns). minSwapsFromStart is always at least 1.
Active today: the result screen shows “Your swaps”, “Min possible”, and the grid. swapsOverMin = max(0, swapCount − minSwapsFromStart); zero gives “Perfect solve”.
Known gap: when a flag has 4 or more tile classes and enumerating their layouts would exceed 750,000 candidates, par falls back to the identity count. That value is an upper bound, so a player can beat “Min possible”, and the clamp reports it as a perfect solve.
Known gap: MAX_COUNTRY_RETRY_ATTEMPTS = 5 is exported from constants.ts and never read.
Known gap: results are client-reported (xpPolicy: "none"), like the other side challenges.

3. Concrete implementation

Shuffle

The shared shuffle is a textbook Fisher–Yates on a copy of the array:

export function shuffleArray<T>(array: T[]): T[] {
  const shuffled = [...array];
  for (let i = shuffled.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
  }
  return shuffled;
}

The puzzle wraps it in a rejection loop so the identity never ships:

export const createShuffledBoard = (tileCount: number) => {
  const solvedBoard = Array.from({ length: tileCount }, (_, index) => index);
  let shuffledBoard = shuffleArray(solvedBoard);
  while (isStrictlySolved(shuffledBoard)) {
    shuffledBoard = shuffleArray(solvedBoard);
  }
  return shuffledBoard;
};

createInitialPuzzleBoard adds a second loop for visual solves: up to MAX_VISUAL_RESHUFFLE_ATTEMPTS = 24 reshuffles, then breakSolvedLayout, which tries every pair swap until one breaks the visual solve. For a flag whose tiles all look the same, usesIdentityPuzzleSolve switches the solve check back to strict identity, so the puzzle stays winnable in a meaningful way.

Swap

A swap is a two-element exchange on a copy of the array, followed by the solve check:

const nextTilesBySlot = [...tilesBySlot];
[nextTilesBySlot[fromSlot], nextTilesBySlot[toSlot]] = [
  nextTilesBySlot[toSlot]!,
  nextTilesBySlot[fromSlot]!,
];

const solved = isPuzzleSolved(nextTilesBySlot, pieceSignatures);
const nextSwapCount = swapCount + 1;

Every swap counts, including swaps of two identical-looking tiles.

Minimum swaps with distinct tiles

export const countCyclesOfPermutation = (mapping: number[]) => {
  const n = mapping.length;
  const seen = new Array<boolean>(n).fill(false);
  let cycles = 0;
  for (let i = 0; i < n; i += 1) {
    if (seen[i]) {
      continue;
    }
    cycles += 1;
    let j = i;
    while (!seen[j]) {
      seen[j] = true;
      j = mapping[j] ?? j;
    }
  }
  return cycles;
};

minSwapsToIdentity returns n − countCyclesOfPermutation(tilesBySlot). Fixed points count as cycles of length 1.

Cycle decomposition of tilesBySlot = [2, 0, 1, 4, 3, 5]. Follow slot → the piece it holds → that piece's home slot. Three cycles, so 6 − 3 = 3 swaps.

Tile signatures

getPieceSignaturesForCountry loads the SVG flag, draws it on a canvas columns × 48 px wide at the flag’s true aspect ratio, and hashes the interior of each tile (a 4 px inset keeps anti-aliased seams out):

const quantizeChannel = (channel: number) =>
  Math.min(255, Math.round(channel / COLOR_QUANTUM) * COLOR_QUANTUM);

export const hashPixelData = (pixelData: Uint8ClampedArray, stride = 8) => {
  let hash = 2166136261;
  for (let index = 0; index < pixelData.length; index += stride) {
    hash ^= quantizeChannel(pixelData[index] ?? 0);
    hash = Math.imul(hash, 16777619);
    hash ^= quantizeChannel(pixelData[index + 1] ?? 0);
    hash = Math.imul(hash, 16777619);
    hash ^= quantizeChannel(pixelData[index + 2] ?? 0);
    hash = Math.imul(hash, 16777619);
  }
  return `${hash >>> 0}`;
};

That is FNV-1a 32-bit over quantized RGB (COLOR_QUANTUM = 32), reading every second pixel (stride 8 bytes) and ignoring alpha. Results are cached per code:columns×rows. If the image fails to decode or the canvas is tainted, the function returns null and the game falls back to strict identity.

Minimum swaps with look-alike tiles

minSwapsToVisualSolve picks a strategy by the number of distinct signatures $K$ :

How par is computed. Every branch returns an exact minimum except the last fallback, which is an upper bound.

The $K \le 3$ path covers most striped flags and avoids the $5!^3 \approx 1.7$ million layouts a 5×3 tricolor would otherwise enumerate:

const { mismatch, misplaced } = buildMismatchMatrix(
  tilesBySlot,
  pieceSignatures,
  colorIndex
);
let cycles = extractTwoCyclesInPlace(mismatch);
if (k === 3) {
  cycles += countResidualThreeCycles(mismatch);
}
return misplaced - cycles;

Tile rendering

Each tile is a <button> whose background is the whole SVG, scaled up and shifted:

export const getBackgroundPercent = (index: number, total: number) => {
  if (total <= 1) {
    return "0%";
  }
  return `${(index / (total - 1)) * 100}%`;
};

with background-size: columns·100% rows·100%. The flag is loaded once and the grid needs no image slicing.

4. Internal mechanics & mathematics

Fisher–Yates is uniform

At step $i$ (counting down from $n-1$ ), the element placed at index $i$ is chosen uniformly from the $i+1$ still unplaced. Each permutation arises from exactly one sequence of choices, so

P(\pi) = \prod_{i=1}^{n-1} \frac{1}{i+1} = \frac{1}{n!}

Rejecting the identity makes the start uniform over the $n! - 1$ other permutations (719 for Easy, about $4.8 \times 10^8$ for Medium, $1.3 \times 10^{12}$ for Hard), before the visual-solve rejection trims a few more.

Minimum transpositions $= n - c(\pi)$

Let $c(\pi)$ be the number of cycles of $\pi$ , fixed points included. The identity is the only permutation with $c = n$ .

Lemma. For any permutation $\pi$ and transposition $\tau = (a\;b)$ , $c(\pi \circ \tau) = c(\pi) \pm 1$ . If $a$ and $b$ lie in the same cycle, the swap splits it in two; if they lie in different cycles, it merges them.

Lower bound. Each swap raises $c$ by at most 1. Going from $c(\pi)$ to $n$ takes at least $n - c(\pi)$ swaps.

Achievability. In a cycle of length $k > 1$ , swap the slot holding some piece with that piece’s home slot. The piece becomes a fixed point and the cycle shrinks to length $k - 1$ , so $c$ goes up by exactly 1. A $k$ -cycle takes $k - 1$ swaps, and the total is

\sum_{\text{cycles}} (k_j - 1) = n - c(\pi)

which meets the lower bound. For the board in the diagram, $6 - 3 = 3$ .

Interactive

Puzzle swap bench

Each tile is a distinct piece, so par is n minus the number of cycles. The production puzzle also treats lookalike tiles as interchangeable; this bench is the distinguishable case from minSwapsToIdentity().

Cycles: 3
Min swaps: 6
Your swaps: 0

Tap a tile, then another, to swap them.

Parity does not block anything

A swap is a transposition, and transpositions generate the full symmetric group $S_n$ . Every shuffled board is solvable, so the code has no solvability check.

Sliding puzzles are different. There, every move swaps the blank with a neighbor, and returning the blank to its home cell takes an even number of moves. Only permutations whose parity matches that constraint are reachable, and half of the scrambles have no solution. The Puzzle challenge has no blank, so the constraint never arises.

Parity still shows up in the score. The sign of a permutation is $\operatorname{sgn}(\pi) = (-1)^{n - c(\pi)}$ , and any sequence of $m$ swaps that reaches the identity satisfies $m \equiv n - c(\pi) \pmod 2$ . On a flag where every tile looks different, swapsOverMin is therefore always even: a player who wastes one swap has to waste a second to undo it. With look-alike tiles there are several target layouts of different parity, and odd overshoots are possible.

Expected par

For a uniformly random permutation, $\mathbb{E}[c] = H_n = \sum_{k=1}^{n} 1/k$ . Conditioning on “not the identity” changes this in the third decimal place for $n = 6$ and less for larger $n$ .

Grid	$n$	$H_n$	Expected par $n - H_n$	Worst case $n - 1$
Easy 3×2	6	2.450	3.55	5
Medium 4×3	12	3.103	8.90	11
Hard 5×3	15	3.318	11.68	14

These hold for flags with all-distinct tiles. Look-alike tiles lower the par.

Look-alike tiles

Group the piece indices by signature: $G_1, \ldots, G_K$ . A layout is visually solved when every slot $s$ holds a piece with the same signature as piece $s$ . The targets are the permutations $\sigma$ that map each group onto itself, and reaching $\sigma$ from $\pi$ costs $n - c(\sigma^{-1} \pi)$ swaps. So

\text{par}(\pi) = n - \max_{\sigma \in G_1! \times \cdots \times G_K!} c(\sigma^{-1}\pi)

The general branch enumerates every $\sigma$ with a depth-first walk over orderings of each group, which is $\prod_j |G_j|!$ candidates, capped at 750,000.

For $K \le 3$ the code uses a closed form. Build a directed multigraph on the $K$ colors with one edge $A \to B$ for each slot of color $A$ that holds a tile of color $B \ne A$ . Let $m$ be the number of such misplaced slots. Every color has equal in-degree and out-degree (as many $A$ tiles sit outside $A$ slots as $A$ slots hold foreign tiles), so the edges split into cycles, and

\text{par} = m - (\text{maximum number of edge-disjoint cycles})

$K = 2$ : $m_{AB} = m_{BA}$ , all cycles are 2-cycles, and par $= m/2$ .
$K = 3$ : greedily removing 2-cycles is optimal. What remains has no opposite edge pairs, and balance forces it to be $t$ copies of one directed triangle. Par $= m - \sum_{i<j}\min(m_{ij}, m_{ji}) - t$ .

Background position

With background-size $k \cdot 100\%$ along an axis and background-position $p$ , CSS shifts the image by $p \cdot (\text{box} - \text{image}) = p(1 - k)\cdot\text{box}$ . Tile $i$ needs a shift of $-i \cdot \text{box}$ , so $p = i / (k - 1)$ , which is getBackgroundPercent.

5. Threat model, failure modes & edge cases

Par above the true minimum. The 750,000 cap can send a flag with 4 or more tile classes and one large group (for example group sizes 8, 3, 2, 2 on a 5×3 grid: $8! \cdot 3! \cdot 2! \cdot 2! \approx 9.7 \times 10^5$ ) to the identity fallback. Par is then too high, and max(0, …) turns a below-par finish into “Perfect solve”.
Signature merges. Tiles that differ only inside the 4 px inset border, or by less than one 32-level quantization step, hash the same and count as interchangeable. The board can be accepted as solved while a thin detail sits in the wrong place.
Hash collisions. Two genuinely different tiles colliding in 32 bits within one board of at most 15 tiles has probability around $15^2 / (2 \cdot 2^{32}) \approx 2.6 \times 10^{-8}$ .
CORS or decode failure. loadFlagImage sets crossOrigin = "anonymous" for cross-origin URLs. If decoding fails or getImageData throws, signatures are null: the solve check becomes strict identity and par uses the distinct-tile formula. The puzzle stays playable but may demand swapping identical-looking tiles.
Race on difficulty change. startNewGame increments gameStartRequest and drops the result of any older async signature load, so switching grids quickly cannot install a stale board.
No integrity check. The board, the par, and the swap count all live in the client. A completion posts guessCount: finalSwapCount best-effort; nothing verifies it.

6. Architectural tradeoffs & non-goals

Choice	Alternative	Why the code does this
Swap any two tiles	Sliding tiles with a blank	No parity trap, no dead scrambles, and the score has a clean closed-form par. Easier on touch screens.
Visual solve via pixel signatures	Require every numbered piece in its home slot	Players cannot tell identical tiles apart; demanding a specific one would feel broken.
Closed form for $K \le 3$ , enumeration otherwise	Always enumerate, or always use the identity count	Enumeration blows up on 5×3 tricolors; the identity count overstates par on striped flags.
Fallback to an upper bound past 750,000	Exact search (for example, max cycle packing)	Bounded latency on a UI thread. The cost is a rare generous “Perfect solve”.
One SVG as a scaled CSS background	Pre-sliced tile images	One request, sharp at any size, and the opaque flag URL is reused.

Non-goals: timed scoring, move undo, preventing a player from reading the answer (the country name is in client state from the start), and server-verified results.