Solving the Number Sums board using mathematical optimization

Challenge solution

The combination of selected numbers (circled) that satisfies all row and column sums is:

Index sets

• \(\mathcal{I} = \{1, \dots, R\}\): Set of rows of the matrix.
• \(\mathcal{J} = \{1, \dots, C\}\): Set of columns of the matrix.

Parameters

• \(A_{ij} \in \mathbb{Z}^+\): Number located in cell $i \in \mathcal{I}, j \in \mathcal{J}$.
• \(R_i \in \mathbb{Z}^+\): Target sum for row $i \in \mathcal{I}$.
• \(C_j \in \mathbb{Z}^+\): Target sum for column $j \in \mathcal{J}$.

Decision variables

• \(x_{ij} \in \{0, 1\}\): Binary variable equal to $1$ if the number in cell $(i,j) \in \mathcal{I} \times \mathcal{J}$ is selected, and $0$ if discarded.

Objective function

\[\min z = 0\]

Required sum in each row:

\[\sum_{j \in \mathcal{J}} A_{ij} x_{ij} = R_i \quad \forall i \in \mathcal{I}\]

Required sum in each column:

\[\sum_{i \in \mathcal{I}} A_{ij} x_{ij} = C_j \quad \forall j \in \mathcal{J}\]

Variable domains:

\[x_{ij} \in \{0, 1\} \quad \forall i \in \mathcal{I}, \; j \in \mathcal{J}\]

Source code

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

GitHub Repository: fjmartincampo/NumberSums