The harmony of digits in solving Kakuro

Image by Mohamed Marey retrieved from Unsplash

Kakuro (popularly known as the number crossword) is one of the world’s most popular logic puzzles. It combines the spatial placement of Sudoku with classic arithmetic combinatorics.

Unlike conventional Sudoku, where the objective focuses on digit permutations, Kakuro requires analyzing numerical combinations that sum to an exact amount without repeating any digit in the same row or column.

Despite its apparent mathematical complexity, the game does not require supernatural skills, but rather deductive logical reasoning, data structuring, and basic combinatorics.

Formal description of the problem

The game is played on a grid made up of white cells (empty), black cells (blocked), and colored cells (with clues):

You must fill each white cell with a single digit from 1 to 9 inclusive.
Each continuous block of white cells (horizontal or vertical) has an associated sum clue located in the colored cell immediately to its left or above.
The sum of the numbers in each block must equal exactly the assigned clue.
No digit can be repeated within the same continuous block of white cells.

To determine the correct assignment, we have the following initial board:

Would you like to try solving it logically before looking at its mathematical formulation?

This puzzle can be formulated as a binary linear optimization model, do you dare to try it?

To solve Kakuro systematically and automatically, we can formulate it as a binary linear optimization model.

Index sets

\(\mathcal{R}\): Set of rows.

\(\mathcal{C}\): Set of columns.

\(\mathcal{W} \subset \mathcal{R} \times \mathcal{C}\): Set of white cells.

\(\mathcal{K} = \{1, 2, \dots, 9\}\): Set of possible numerical values.

\(\mathcal{H}\): Set of horizontal blocks. For each \(h \in \mathcal{H}\), \(\mathcal{S}_h \subset \mathcal{W}\) is the set of its cells.

\(\mathcal{V}\): Set of vertical blocks. For each \(v \in \mathcal{V}\), \(\mathcal{S}_v \subset \mathcal{W}\) is the set of its cells.

Parameters

\(V_h\): Target sum of cell values in row block \(h \in \mathcal{H}\).

\(V_v\): Target sum of cell values in column block \(v \in \mathcal{V}\).

Decision variables

\(x_{rck} = 1\) if white cell \((r,c) \in \mathcal{W}\) takes digit \(k \in \mathcal{K}\), and \(0\) otherwise.

Since we are solving a logical feasibility problem, the objective function can be a constant:

Objective function
\[\min z = 0\]

We now define the rules of Kakuro as linear constraints:

Each white cell must contain exactly one digit:
\[\displaystyle \sum_{k \in \mathcal{K}} x_{rck} = 1 \quad \forall (r,c) \in \mathcal{W}\]

Satisfying sums in horizontal blocks:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_h} \sum_{k \in \mathcal{K}} k x_{rck} = V_h \quad \forall h \in \mathcal{H}\]

Uniqueness of digits in horizontal blocks:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_h} x_{rck} \leqslant 1 \quad \forall h \in \mathcal{H}, \; k \in \mathcal{K}\]

Satisfying sums in vertical blocks:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_v} \sum_{k \in \mathcal{K}} k x_{rck} = V_v \quad \forall v \in \mathcal{V}\]

Uniqueness of digits in vertical blocks:
\[\displaystyle \sum_{(r,c) \in \mathcal{S}_v} x_{rck} \leqslant 1 \quad \forall v \in \mathcal{V}, \; k \in \mathcal{K}\]

Variable domains
\[x_{rck} \in \{0, 1\} \quad \forall (r,c) \in \mathcal{W}, \; \forall k \in \mathcal{K}\]

Source code

The GAMS / Python implementation of the optimization model presented in this post is available in the GitHub repository.

GitHub Repository: fjmartincampo/Kakuro

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.

The harmony of digits in solving Kakuro

Formal description of the problem

Challenge solution

Source code

Enjoy Reading This Article?