DEV Community

Generating Row-and-Column Sum Puzzles That Have Exactly One Solution

Creating a satisfying logic puzzle means more than just setting a target - it demands a unique solution. For row-and-column sum puzzles (where you strike out numbers so the remaining ones match given row and column totals), ensuring uniqueness is both essential and non-trivial.

This post explains how a simple JavaScript generator creates puzzles with exactly one solution, using only deterministic algorithms and a seeded PRNG.

The puzzle format is straightforward: a grid of numbers 1-9, with some cells optionally marked as "golden" (counting double when kept). The player must determine which cells to keep so that the sum of kept values (with golden cells doubled) matches the row and column targets.

The Generator Workflow

The generator begins by initializing a seeded random number generator using the mulberry32 style - fast, deterministic, and suitable for reproducible puzzle generation.

  • Grid size: makePuzzle(rows, cols, gold, seed) takes the grid dimensions, the number of golden cells and a seed.
  • Golden cell placement: Randomly select positions for golden cells, avoiding duplicates.
  • Hidden answer: Generate a candidate solution by keeping each cell with a probability of roughly 56%. This is done iteratively, rejecting any configuration where:
    • A row or column keeps all or no cells.
    • The total kept cells are less than 40% or more than 72% of the grid.
  • Compute targets: For each row and column, sum the kept values, doubling those in golden cells. These become the rowT and colT values.

This produces a valid puzzle instance with a known solution. But we’re not done - we must ensure uniqueness.

Ensuring a Single Solution

The key challenge is verifying that only one valid configuration of kept cells satisfies all row and column targets. The solution uses a pruning backtracking search:

  • For each row, precompute all possible subsets (bitmasks) of cells that sum to the row target, accounting for golden cells.
  • Since grids are small (max 6 cells per row), there are at most 64 possible masks per row - a manageable number.
  • Then, search row by row: for each row, try every valid mask, update partial column sums, and prune early if any column sum exceeds its target.
  • When all rows are processed, check if all column sums exactly match their targets.

We count the number of complete solutions. If the count is exactly 1, the puzzle is accepted. Otherwise, we increment the seed and regenerate - up to 400 attempts.

This approach is fast because:

  • Row masks are precomputed and small.
  • Column pruning eliminates large branches early.
  • The search space is bounded by the structure of the puzzle.

The solution counter

This is the core of countSol in the repository, lightly trimmed. val and mult are flat arrays (mult is 2 for a golden cell and 1 otherwise), rowT and colT are the targets, and opts[r] holds the masks that already meet the target of row r.

const col = new Array(C).fill(0);
let count = 0;
function rec(r) {
  if (r === R) {
    for (let c = 0; c < C; c++) if (col[c] !== colT[c]) return false;
    count++;
    return count >= limit; // stop early once we have seen enough
  }
  for (const m of opts[r]) {
    let ok = true;
    for (let c = 0; c < C; c++) if (m >> c & 1) {
      col[c] += val[r * C + c] * mult[r * C + c];
      if (col[c] > colT[c]) ok = false; // this column is already over its target
    }
    if (ok && rec(r + 1)) return true;
    for (let c = 0; c < C; c++) if (m >> c & 1) col[c] -= val[r * C + c] * mult[r * C + c];
  }
  return false;
}
rec(0);

Testing and Validation

Running npm test produces 80 puzzles across sizes 3Γ—3 to 6Γ—6, with 0 to 3 golden cells and 20 seeds per configuration. Each test asserts:

  • The puzzle has exactly one solution.
  • The stored hidden answer satisfies all row and column targets.

These are property checks on the generator, not a proof, but they catch the usual mistakes such as forgetting to count a golden cell twice.

Usage example

const { makePuzzle, countSol } = require('./index.js');
const P = makePuzzle(4, 4, 1, 42); // rows, columns, golden cells, seed
console.log(P.rowT, P.colT); // [ 4, 16, 10, 8 ] [ 8, 11, 12, 7 ]
console.log(countSol(P, 3).count); // 1

That call builds a 4 by 4 grid with one golden cell. The row targets are 4, 16, 10 and 8, the column targets are 8, 11, 12 and 7, and the solver confirms there is one way to meet all of them.

Repository and Game

The full implementation is open-source and available at: https://github.com/tadjim339-links/sumgrid-puzzle (MIT license).

The same generator powers a free browser game, where puzzles are presented in a garden-themed interface. If you’d like to try them in a playful setting, check it out here: play the garden version of these math puzzles

Final Thoughts

Generating puzzles with a single solution isn’t magic - it’s careful design. By combining seeded randomness, structured validation, and efficient pruning, we create puzzles that are both solvable and satisfying.

The same seed always gives the same puzzle, which makes bugs easy to reproduce and levels easy to number.

Read on DEV Community ↗ ← Back to News

Comments

No comments yet. Start the discussion.