Detailed mathematical approach

Problem Summary

Each puzzle is a Kakuro grid whose clue sums are written with letters \(A,\dots,J\) instead of decimal digits. The same bijection between those ten letters and the ten digits \(0,\dots,9\) is used everywhere in the puzzle, so solving one grid means recovering a single global permutation of the digits. Every white cell contains a value from \(1\) to \(9\), digits may not repeat inside one horizontal or vertical run, and each run must add up to the number represented by its clue.

After a puzzle is solved, the digits assigned to \(A,B,\dots,J\) are concatenated in that order to form one encrypted 10-digit number. The Project Euler task asks for the sum of those encrypted values over the full dataset.

Mathematical Approach

1. Variables and Global Constraints

Let \(L_0,\dots,L_9\) denote the digits assigned to the ten letters. They satisfy

$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$

For each white cell \(c\), introduce a cell variable \(x_c\in\{1,\dots,9\}\). If that cell is labelled by letter \(i\), then the cell and the letter must agree:

$x_c=L_i.$

This already yields useful pruning. Letters may use \(0\), but white cells may not, so every letter that appears in a white cell is immediately restricted to \(\{1,\dots,9\}\).

2. Runs as Ordered Distinct-Digit Tuples

A Kakuro run is an ordered list \(R=(c_1,\dots,c_\ell)\) of consecutive white cells. For a run of length \(\ell\) and sum \(s\), the relevant object is the set

$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$

The order matters, because \((1,2,3)\) and \((3,2,1)\) fill different cells. The implementation therefore precomputes all ordered tuples for every \(\ell\le 9\) and every achievable sum \(s\le 45\). The total size of this library is

$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$

which is large enough to power strong propagation, but still a fixed constant for this problem.

3. Decoding One-Letter and Two-Letter Clues

If a clue contains one letter \(a\), its numeric value is simply

$s=L_a.$

If a clue contains two letters \(ab\), it is read as a decimal number:

$s=10L_a+L_b,\qquad L_a\neq 0.$

Because a Kakuro run built from distinct digits \(1,\dots,9\) can never exceed \(45\), only clue sums in \([0,45]\) are relevant. That gives immediate pruning on clue letters before search. The solver also treats repeated two-letter clues such as \(aa\) correctly; in that case the sum has the form \(s=11L_a\).

4. Constraint Propagation on a Run

During solving, each cell and each letter has a current domain \(D(\cdot)\). For a fixed run \(R=(c_1,\dots,c_\ell)\), one first computes the set of currently allowed sums. For a one-letter clue \(a\), this is

$S_R=\{d\in D(a): 0\le d\le 9\}.$

For a two-letter clue \(ab\), it is

$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$

A tuple \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) is feasible exactly when every coordinate matches the current domain of its cell:

$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$

Let \(\mathcal F_R\) be the set of all feasible tuples over all allowed sums. Then each cell can be pruned by projection:

$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$

If no feasible tuple survives, the current branch is inconsistent and can be abandoned immediately.

The same information is projected back to the clue letters. A one-letter clue keeps only digits that still occur as valid run sums. A two-letter clue keeps only digit pairs whose decimal value \(10u+v\) still occurs among feasible sums. This two-way filtering between clue digits and run digits is the main reason the search tree stays small.

5. Global All-Different Pruning

The ten letters must form a permutation of \(0,\dots,9\). Instead of a heavy general matching algorithm, the implementation repeatedly applies two light but effective reductions.

First, if a letter is already fixed to one digit, that digit is removed from all other letter domains. Second, if a digit appears in only one remaining letter domain, that letter is forced to take it. In constraint-programming language these are singleton elimination and hidden-single detection for the global all-different condition.

6. Search Strategy and Final Value

Propagation often solves most of a puzzle by itself. When it does not, the solver chooses the unresolved variable with minimum remaining domain size, considering both letters and white cells, and branches on its candidate digits. After each tentative assignment, the full propagation cycle runs again. This is the standard minimum-remaining-values heuristic combined with depth-first search.

Once all letters are fixed, the encrypted value of one puzzle is

$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$

The required answer is the sum of \(E\) over all puzzles in the input.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. They parse one puzzle into white cells, letter-labelled white cells, and horizontal or vertical runs. Next they build the tuple tables \(\mathcal T_{\ell,s}\), initialize each letter with domain \(\{0,\dots,9\}\), and initialize each white cell with domain \(\{1,\dots,9\}\).

The propagation loop alternates between three ideas: linking letter domains to labelled cells, pruning the global letter permutation, and scanning each run against the precomputed tuple tables. If propagation no longer changes anything and the puzzle is still incomplete, the implementation branches on the smallest non-singleton domain and recurses. The three language versions differ only in syntax; algorithmically they are the same solver.

Complexity Analysis

The worst-case complexity remains exponential, because Kakuro solving with a global digit substitution still requires backtracking in difficult cases. However, the expensive combinatorial structure is mostly front-loaded into a constant-size precomputation. For this problem the tuple library has fixed size \(986409\), so it does not grow with the number of puzzles.

If a run has length \(\ell\), one propagation pass examines at most the tuples attached to sums that are still allowed by its clue. A rough upper bound for one pass over that run is

$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$

The overall runtime is therefore dominated by the number of search nodes that survive propagation. In practice, tuple filtering, clue back-projection, all-different pruning, and MRV branching reduce that number sharply. Memory usage is linear in the current puzzle state plus the fixed tuple table.

References

1. Problem page: https://projecteuler.net/problem=424
2. Kakuro overview: Wikipedia - Kakuro
3. Constraint satisfaction problem: Wikipedia - Constraint satisfaction problem
4. Variable ordering heuristics: Wikipedia - Variable and value ordering heuristics
5. Global constraints in constraint programming: Wikipedia - Constraint programming