Solving Kakurasu: every line is a subset sum, and the size dial is the difficulty dial

Kakurasu in the browser with two sound rule sets inside. Shade
cells on an n×n grid so every row and column hits its target, where a
shaded cell is worth its position — column j scores j into its row,
row i scores i into its column. Strip the board away and every line
asks the same question: which subset of the weights 1..n sums to the
target? The human move is interval arithmetic; the machine move is
full enumeration. I implemented both, cross-checked them against an
independent solver, and measured the gap: intervals finish 99% of 4×4
boards on their own and 12.5% of 8×8 boards. Solver-backed puzzle #21.

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

Peel the board and one constraint remains

Kakurasu's rules fit in a paragraph. Shade cells on an n×n grid. A shaded
cell in row i, column j adds j to its row's score and i to its
column's score. Match all 2n targets and you win.

Twenty puzzles into this series, this is the first one with exactly
one kind of constraint. Nurikabe has connectivity, Slitherlink has a
loop, Dominosa has the two sides of an exact cover. Kakurasu doesn't.
Rows and columns, stripped of their coordinates, all ask:

which subset of the weights {1, 2, ..., n} sums to the target?

The board is that question asked 2n times, and lines only interact by
sharing cells. So the design is one sentence: write one line solver,
run it over 2n lines to a fixpoint.

export interface Line {
  kind: 'row' | 'col';
  index: number;
  cells: number[];   // in weight order: position k carries weight k+1
  target: number;
}

The human rules: interval arithmetic

Let rem be what a line still owes (target minus the shaded sum). What a
person actually does at a Kakurasu board reduces to two moves:

too-big     : w > rem          → that weight can never fit — cross it
cannot-skip : Σw - w < rem     → the rest can't cover for it — shade it

That is bounds consistency on a subset sum: compare rem against the
interval of reachable sums, O(n) per line. A target-0 line going all
crosses and a target-n(n+1)/2 line going all shades are just its special
cases.

The machine rule: enumerate everything

The machine can do strictly better on the same line. There are at most
n ≤ 9 undecided cells, so list every subset that sums to rem — at
most 2⁹ = 512 masks — and keep only what all witnesses agree on. A cell
in every witness gets shaded, a cell in no witness gets crossed, zero
witnesses is a contradiction.

for (let mask = 0; mask < 1 << u; mask++) {
  let sum = 0;
  for (let k = 0; k < u; k++) if (mask & (1 << k)) sum += weights[k];
  if (sum === rem) { witnesses++; inAll &= mask; inAny |= mask; }
}

This is arc consistency on the line. Nothing sound can extract more from
one line alone.

And the gap between the two rule sets is real. Over weights {1,2,3,4}
with rem = 6, the witnesses are {2,4} and {1,2,3} — both contain
weight 2, so the 2 is forced. The interval rules stay silent: 2 ≤ 6, so
too-big doesn't fire; 10 − 2 = 8 ≥ 6, so cannot-skip doesn't either.
The mirror case exists too: over {1,2,3} with rem = 5 the only witness
is {2,3}. Intervals do force the 2 and the 3, but only enumeration can
cross the 1 — at 1 ≤ 5, the interval eye keeps seeing a weight that
might still fit.

The Hint button runs both sets in order — intervals first, then
enumeration — and quotes whichever rule fires: "Without weight 4,
row 3 cannot reach its target — shade it." Every hint arrives with its
reason attached.

The measurement: the size dial is the difficulty dial

Both rule sets are sound, so choosing between them is a performance
question, not a correctness one — which means it can be measured. I
generated 200 boards per size and ran each rule set to its fixpoint, no
guessing:

size	intervals finish	enumeration finishes	rolls to unique	search nodes when needed
4×4	99%	100%	1.02	—
5×5	88%	99.5%	1.07	1.0
6×6	66%	95.5%	1.14	1.3
7×7	27.5%	76.5%	1.51	3.7
8×8	12.5%	43.5%	2.44	12.2

A 4×4 Kakurasu is nearly trivial for anyone who can run interval
arithmetic. At 8×8, intervals alone finish one board in eight, and even
per-line enumeration — the strongest sound thing a single line supports —
stalls on more than half.

The reason is the structure of the weights. The subset sums of 1..n get
denser as n grows: more subsets hit the same target, which means
more witnesses per line, which means "all witnesses agree" happens less
and less. Fewer cells get forced. Kakurasu's difficulty curve is a
direct image of how degenerate the subset sums of 1..n are — the
felt experience that big boards suddenly stop yielding moves has an
exact combinatorial backing.

Measuring also exposed a selection effect I didn't expect. On 6×6 boards
where enumeration stalls, it stalls having decided an average of 5.5
of 36 cells — essentially at move zero. Interval stalls average 12.3
cells. Enumeration strictly dominates intervals, so the boards that
defeat it are precisely the boards where nothing was ever deducible.
The stronger rule fails quietly and fails early — you only see this by
measuring progress-at-failure, not success rates.

Stalled boards go to search: branch a cell shaded/crossed, propagate
each side to its fixpoint, recurse. As the table shows, even when search
is needed it averages a dozen nodes — Kakurasu never gets deep. The test
suite also pins the monotonicity: exact search never expands more nodes
than bounds search on the same board.

Soundness is pinned by cross-checking

On the previous puzzle in this series (Dominosa), a subtly unsound
propagation rule certified two-solution boards as unique, and what
caught it was a diagnostic that compared solution counts across rule
sets. That check is now standard equipment: sound rule sets must agree
on solution counts when combined with exhaustive search.

So this repo carries a third solver that shares no code with the
propagators: enumerate, per row, every subset hitting that row's target,
sweep the cartesian product with running column sums, prune overshoots,
and demand exact column targets at the bottom. Sound and complete by
construction.

// verification only: row candidates × column-sum pruning,
// no code shared with the propagators
export function countSolutionsByRows(puzzle: Puzzle, cap = Infinity): number

The test streams 120 random target boards — satisfiable or not — through
search-with-intervals, search-with-enumeration, and the row solver, and
requires all three counts to be identical. Slip one unsound rule into
the propagators and this is the test that fires first.

Generation: no clues to remove, again

Kakurasu has no hint cells. The 2n targets are the puzzle. So the
series' usual generator — build a solved board, greedily delete clues
while uniqueness survives — has nothing to delete. Generation falls back
to rejection sampling: shade each cell with probability ½, induce the
targets, and accept only when the counting search proves the solution
unique. That takes 1.02 rolls at 4×4 and still only 2.44 at 8×8 —
uniqueness is a common property here, and rejection sampling is the
algorithm.

Small boards allow a census. Folding all 512 boards of the 3×3 case
shows exactly one ambiguous target board: every row and column
summing to 3, where {3} and {1,2} trade places. At 2×2 ambiguity is
impossible — the four subset sums of {1,2} are all distinct, so a line
is recoverable from its target. The puzzle's entire source of difficulty
— degenerate subset sums — shows its face in the smallest possible
census.

Takeaways

• When peeling a puzzle leaves one kind of constraint, the whole solver is one line solver plus a fixpoint loop. Implementation size tracks the number of constraint kinds, not the number of rules.
• Implementing both the human rule set and the machine rule set for the same constraint turns a puzzle's difficulty curve into a statistic: which rules does a board require? For Kakurasu that curve is a function of subset-sum density over 1..n.
• Strong rules fail selectively, on boards where nothing was ever deducible. Measure progress at failure, not just success rates.
• Agreement on solution counts across sound rule sets is the cheapest detector of unsound propagation. A verification solver that shares no code with the thing it checks pays for itself every time.
• 56 tests, TypeScript, zero runtime dependencies.

All the code is public: https://github.com/sen-ltd/kakurasu