DEV Community

SEN LLC
SEN LLC

Posted on

Solving Kakuro (Cross Sums) with Constraint Propagation — Sum-Combination Domains, Fewest-Candidate Search, and Puzzles Proven Unique

#typescript #algorithms #constraintsolving #gamedev

Kakuro (cross sums / 加算クロス), the addition logic puzzle, built for the
browser with a constraint-propagation solver inside. Three hinges:
(1) every run turns its clue into a domain — of all the ways to pick
k distinct digits that total the clue, the union of every valid
combination is exactly the digits that can appear, so each cell keeps only
what some completion actually uses. Each step is a strict implication, never a
guess. (2) When logic stalls, a backtracking search takes the cell with
the fewest candidates, tries each digit, lets propagation prune, and
proves the answer is unique. (3) Every bundled board is authored as a
filled digit grid — the solver reads the clues off the answer, so picture and
solution can't drift. Solver-equipped puzzle #8.

🌐 Live demo: https://sen.ltd/portfolio/kakuro/
📦 GitHub: https://github.com/sen-ltd/kakuro

Kakuro

The rules, and the logic that follows

A Kakuro grid is white cells and shaded clue cells. White cells group into
runs — maximal horizontal or vertical strips of two-or-more cells. The
shaded cell left of a horizontal run carries its across sum; the one above a
vertical run carries its down sum. A solution fills every white cell with a
digit 1–9 so that, for every run:

  1. Sum — its digits total the clue.
  2. Distinct — no digit repeats.

Both rules become strict deductions — no guessing:

  • Sum combinations. For a run that still needs k digits totalling s, enumerate every size-k subset of 1–9 that sums to s. Their union is exactly the digits that can appear, so each open cell keeps only digits some valid completion uses. A pair summing to 3 must be {1,2}; a pair summing to 17 must be {8,9}; a triple summing to 6 must be {1,2,3}.
  • Distinctness. A digit pinned in one cell is struck from every other cell in the same run.

Digits are bitmasks over 1–9 and a cell's domain is the set still possible
for it. propagate() runs both rules to a fixpoint, recording the order
cells were pinned — exactly what the demo's Hint replays, one guess-free step
at a time.

if (dup || fixedSum > run.sum) return { ok: false, forced };  // run broken
const allowed = comboUnion(pool, remCount, remTarget);        // sum-combo union
if (allowed === 0) return { ok: false, forced };              // no completion
for (const j of open) if (!shrink(j, allowed)) return { ok: false, forced };
Enter fullscreen mode Exit fullscreen mode

comboUnion walks digits in ascending order, so if (d > rem) break prunes the
whole tail the moment the smallest remaining digit overshoots — no wasted
branches.

When logic stalls: search that proves uniqueness

Some boards need a guess. The backtracking solver takes the cell with the
fewest candidates (minimum-remaining-values), tries each digit, and lets
propagation prune. solveAll enumerates up to a limit; hasUniqueSolution
stops at two, and the test suite asserts every bundled puzzle stops at exactly
one.

export function hasUniqueSolution(puzzle: Puzzle): boolean {
  return solveAll(puzzle, 2).length === 1;
}
Enter fullscreen mode Exit fullscreen mode

Same philosophy as the Sokoban (#286), Nonogram (#287), Slitherlink (#288) and
Akari (#289) entries: ship your levels through your solver.

Puzzles are solver-verified, not hand-keyed

Each board is authored as nothing but a filled digit grid — # and the
digits 1–9. The solver does the rest:

  1. Sum every run of the solution and write that total onto its head as the across/down clue.
  2. Require the resulting clued board to be unique (reject the layout otherwise).

So the answer grid is the single source of truth and the clues are derived from
it — they cannot disagree. The tests re-solve the finished board and assert the
digits match:

expect(hasUniqueSolution(puzzle)).toBe(true);  // exactly one answer
expect(solved[i]).toBe(solution[i]);           // and it's the authored grid
Enter fullscreen mode Exit fullscreen mode

The five bundled boards (5×5 to 8×8, every white cell woven into both an across
and a down run) were found by random-fill search over fixed layouts, kept only
where the derived clues force a single solution.

Takeaway

Kakuro goes a long way on fixpoint propagation of sum-combination domains,
and when that stalls, fewest-candidate search proves the unique answer. That
makes eight solver-equipped puzzles — Sudoku, Lights Out (GF(2)), the 15-puzzle
(parity + IDA*), Sokoban (pull-BFS), Nonogram (constraint propagation),
Slitherlink (edge propagation), Akari (illumination propagation), and Kakuro
(sum-combination domains + a uniqueness proof) — each wearing a different piece
of mathematics. Hit Solve and watch the grid fill in.

🌐 Live demo: https://sen.ltd/portfolio/kakuro/
📦 GitHub: https://github.com/sen-ltd/kakuro

Top comments (0)