DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

My Kakuro Solver's Baseline Was Solving a Different Puzzle, and the Page Asserted They Agreed

#algorithms #javascript #programming #puzzle

Kakuro is a crossword made of sums. Each run of white cells carries a clue, the digits come from 1 to 9, and no digit repeats inside a run. That last rule is the whole puzzle — it turns a clue into a question about which sets of distinct digits hit a total.

👉 Live, runs in your browser: https://dev48.in/game/day82-kakuro.html

I built the page to show one thing: candidate sets beat raw arithmetic. It did show that. It also showed me three defects in my own code, and none of them was the one I first went looking for.

Defect 1: it never finished

The comparison was supposed to be "solver with candidate sets" against "solver with only a running-total check". The second one hung. Not slow — hung:

$ timeout 120 node kakuro.mjs
$ echo $?
143
Enter fullscreen mode Exit fullscreen mode

Exit 143 is SIGTERM. Nine white cells is 9⁹ = 387,420,489 assignments, and a running total only prunes after it has already overshot.

The fix was not to make it faster. It was to give it a budget and report hitting it:

board white cells rules only with candidate sets
the smallest cross 4 138 46
a 16-in-two corner 4 4,210 27
three across, three down 9 did not finish in 2,000,000 750
an L of runs 5 53,782 27
a 4×4 with a hole 6 34,933 144

"Did not finish in two million nodes" is a stronger claim than any speedup ratio. A ratio invites you to imagine the baseline eventually getting there.

Defect 2: the baseline was solving a different puzzle

Giving it a budget made it terminate, which let me compare solution counts for the first time. They disagreed:

the smallest cross   withC sols 1   |   sumOnly sols 2
Enter fullscreen mode Exit fullscreen mode

The real puzzle has exactly one solution. My baseline found two.

Distinctness-within-a-run had been sitting behind the useCandidates flag:

function allowed(ri, d) {
  if (st.sum + d > run.clue) return false;
  if (!useCandidates) return true;          // <-- everything below is skipped
  if (st.used & (1 << (d - 1))) return false;   // distinctness lived HERE
  ...
}
Enter fullscreen mode Exit fullscreen mode

So "no pruning" also meant "repeats allowed". That is not a slower solver, it is a different puzzle. And the page's self-check said:

the candidate-set solver finds exactly what the sum-only solver finds — the prune is sound, it discards no solution

It was comparing two different games and reporting that they agreed.

Distinctness is a rule, not an optimisation. It belongs above the flag:

if (st.sum + d > run.clue) return false;      // rule: never overshoot
if (st.used & (1 << (d - 1))) return false;   // rule: digits in a run are DISTINCT
if (!useCandidates) return true;              // everything below is inference
Enter fullscreen mode Exit fullscreen mode

Everything above the flag is a rule both solvers must obey. Everything below only changes how fast the same answer is reached.

Defect 3: a self-check that was wrong about the arithmetic 

t("and 16 in two cells is NOT forced", () => combinations(2, 16).length === 2,
  "7+9 and... only 7+9 at length 2");
Enter fullscreen mode Exit fullscreen mode

It failed, and it was right to. Two distinct digits summing to 16: 8+8 repeats, so {7,9} is the only pair. 16-in-two is as forced as 17-in-two. The label even argued itself out of the claim mid-sentence.

That is why the board I named "a 16-in-two corner" has no solutions at all rather than several.

Counting the same thing three ways

The all-23 board has 12 solutions. I did not want to take my own solver's word for it:

  1. Cell-at-a-time search (the page's solver): 12
  2. Run-at-a-time search — place a whole permutation of a valid combination per run, sharing no code with the first: 12
  3. Combinatorics. The only three distinct digits summing to 23 are {6,8,9}, since the maximum is 9+8+7=24. So every row and every column is a permutation of one 3-set — the board is a 3×3 Latin square on three symbols, and there are exactly 3! × 2 = 12.

Three routes, one number.

What I would take from it

The budget did not just stop a hang. Making the baseline terminate is what made its answers comparable, and comparing them is what exposed that it had never been the same puzzle. A test that cannot finish is not a weak test — it is a test that has never actually run, and it will agree with you forever.

Verified by a run-at-a-time solver plus the Latin-square count: 2,062 asserts, 0 failures. 28 in-page checks.

Top comments (0)