Generating puzzles with exactly one solution: Sudoku, Nonogram and a daily seed, in plain JavaScript

When I built a set of browser puzzle games meant to run on e-ink readers (E-Ink Games), one requirement shaped almost every piece of code: every puzzle must have exactly one solution. On a slow, paper-like screen nobody wants to guess and backtrack; the fun is pure deduction. That turned out to be a nice little algorithms problem, so here is a simplified version of how generators like these work, with code you can lift.

Why "exactly one solution" matters

A Sudoku or Nonogram with two valid solutions forces the player to guess at some point. Guessing on a phone is annoying. Guessing on an e-ink display, where every mistaken fill costs a visible refresh, is miserable. It also breaks the promise that "logic is always enough", which is the whole appeal of these puzzles.

So the generator pipeline is always:

1. Produce a random complete solution.
2. Remove information (clues) while a solver confirms the solution is still unique.
3. Stop when the target difficulty is reached.

The trick is step 2: you need a solver that can count solutions, and it needs to stop at 2.

Sudoku: fill, then dig

Step 1: a random full grid

Backtracking with shuffled candidates gives you a uniformly-ish random valid grid quickly:

function shuffle(a) {
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(rand() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function canPlace(g, idx, n) {
  const r = Math.floor(idx / 9), c = idx % 9;
  const br = r - (r % 3), bc = c - (c % 3);
  for (let k = 0; k < 9; k++) {
    if (g[r * 9 + k] === n || g[k * 9 + c] === n) return false;
    if (g[(br + Math.floor(k / 3)) * 9 + bc + (k % 3)] === n) return false;
  }
  return true;
}

function fill(g, idx = 0) {
  if (idx === 81) return true;
  if (g[idx]) return fill(g, idx + 1);
  for (const n of shuffle([1,2,3,4,5,6,7,8,9])) {
    if (canPlace(g, idx, n)) {
      g[idx] = n;
      if (fill(g, idx + 1)) return true;
      g[idx] = 0;
    }
  }
  return false;
}

Step 2: count solutions, but stop at two

function countSolutions(g, limit = 2) {
  // pick the empty cell with the fewest candidates (MRV heuristic)
  let best = -1, bestCands = null;
  for (let i = 0; i < 81; i++) {
    if (g[i]) continue;
    const cands = [];
    for (let n = 1; n <= 9; n++) if (canPlace(g, i, n)) cands.push(n);
    if (cands.length === 0) return 0;
    if (!bestCands || cands.length < bestCands.length) { best = i; bestCands = cands; }
    if (cands.length === 1) break;
  }
  if (best === -1) return 1; // grid full
  let total = 0;
  for (const n of bestCands) {
    g[best] = n;
    total += countSolutions(g, limit - total);
    g[best] = 0;
    if (total >= limit) break;
  }
  return total;
}

The minimum-remaining-values heuristic is what keeps this fast enough to run on a Kindle's modest CPU. Without it, an Expert board with ~22 clues can take noticeably long to verify.

Step 3: dig holes

function makePuzzle(targetClues) {
  const solution = new Array(81).fill(0);
  fill(solution);
  const puzzle = solution.slice();
  for (const i of shuffle([...Array(81).keys()])) {
    if (81 - puzzle.filter(v => !v).length <= targetClues) break;
    const keep = puzzle[i];
    puzzle[i] = 0;
    if (countSolutions(puzzle.slice()) !== 1) puzzle[i] = keep; // put it back
  }
  return { puzzle, solution };
}

Clue count is a rough proxy for difficulty. In the live game, easier boards give around forty givens and Expert leaves just over twenty. A better difficulty metric is "which techniques does a human-style solver need" (naked singles only vs. pairs vs. X-wings), and that is a good next step if you want finer control.

Nonogram: the uniqueness problem is harder

A nonogram's clues are the run lengths of filled cells in each row and column. Generating a random picture is trivial; the problem is that most random pictures are ambiguous. Two different grids can share the same clues (the classic 2×2 checkerboard is the smallest example).

A practical approach:

1. Generate a random grid at a target fill density (around 50–60% keeps it interesting). Mirroring it gives a symmetric, more "picture-like" result.
2. Compute clues.
3. Run a line solver: repeatedly, for each row/column, enumerate all placements of its runs consistent with already-known cells, and mark cells that are filled (or empty) in every placement.
4. If line solving alone determines the whole grid, the puzzle is uniquely solvable by logic. If it stalls, regenerate.

// All placements of runs `clue` in a line of length n, consistent with known cells
function* placements(clue, n, known, pos = 0, i = 0, line = []) {
  if (i === clue.length) {
    const rest = Array(n - pos).fill(0);
    const full = line.concat(rest);
    if (full.every((v, k) => known[k] === -1 || known[k] === v)) yield full;
    return;
  }
  const remaining = clue.slice(i).reduce((a, b) => a + b, 0) + (clue.length - i - 1);
  for (let start = pos; start + remaining <= n; start++) {
    const seg = Array(start - pos).fill(0).concat(Array(clue[i]).fill(1));
    if (i < clue.length - 1) seg.push(0);
    const next = line.concat(seg);
    if (next.every((v, k) => known[k] === -1 || known[k] === v))
      yield* placements(clue, n, known, next.length, i + 1, next);
  }
}

Intersecting all placements per line and iterating until nothing changes is exactly what a human does ("overlap from both ends"), so "line-solvable" is a great definition of "fair". It is stricter than "unique" (some unique puzzles need lookahead), and that strictness is a feature for a casual game.

Boards in the game are 5×5, 10×10 and 15×15. For 15×15 the enumeration can explode on long lines with many short runs; caching placements per (clue, known-mask) keeps it manageable.

Daily puzzles without a server

Both the Wordle-style word game and the daily nonogram give every player worldwide the same puzzle on the same day, with no backend. The idea: derive a seed from the date, feed it to a small deterministic PRNG, and run the same generator.

function hashString(s) {
  let h = 2166136261 >>> 0;              // FNV-1a
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  return h >>> 0;
}

function mulberry32(a) {
  return function () {
    a |= 0; a = (a + 0x6D2B79F5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

const today = new Date().toISOString().slice(0, 10); // pick one timezone convention!
let rand = mulberry32(hashString("nonogram:" + today));

Two gotchas:

• Never use Math.random() anywhere in the generator path once you go deterministic, or players will get different boards.
• Pick a timezone convention and stick to it, otherwise players on different sides of midnight disagree about which puzzle is "today".

Bonus: an unbeatable Tic-Tac-Toe

The Hard mode of the Tic-Tac-Toe game is plain minimax. With only 9 cells the full tree is tiny (< 550k nodes without pruning), so no alpha-beta or memoization is needed even on an e-reader. The best a human can do is a draw, which is a surprisingly fun challenge in itself.

Takeaways

• Generate a full solution, remove clues, and verify uniqueness with a solver that stops at 2.
• MRV makes Sudoku counting fast enough for weak hardware.
• For nonograms, "solvable by line logic" is a better target than "unique".
• Date-seeded PRNGs give you daily shared puzzles with zero backend.

If you want to see these generators in action, all ten games (Sudoku, Nonogram, Minesweeper, 2048, Word Daily and more) are free at games.e-ink.me, no account and no ads. They are designed for Kindle and BOOX browsers but work fine on a desktop too.