Killer Sudoku, the empty board challenge that math can solve

Image by Mohamed Marey retrieved from Unsplash

Killer Sudoku (or Sudoku Killer) is one of the most exciting and challenging variants of classic Sudoku. It combines the spatial positioning logic of traditional Sudoku with the basic arithmetic of Kakuro.

At first glance, the board can seem intimidating because there are no starting numbers filled in the grid. Instead, the board is divided into groupings of cells or “cages”, marked with colored or dashed lines, each featuring a small number in its top-left corner.

Myth says you need to be a mathematical genius to solve the most advanced levels in your head, but the reality is that Killer Sudoku doesn’t require supernatural skills, it requires deductive logical reasoning, data structuring, and knowing the Rule of 45 (the sum of numbers 1 through 9 in any row, column, or block is always 45).

Formal description of the problem

The goal of Killer Sudoku is the same as in regular Sudoku: fill each row, column, and $3 \times 3$ region once with the numbers from 1 to 9. The difference lies in how those numbers are deduced.

The specific rules of Killer Sudoku are as follows:

You must fill all rows, columns, and $3 \times 3$ regions with numbers from 1 to 9, just like in standard Sudoku.
Each cell is part of a cage, indicated by borders of different colors or dashed lines.
The sum of the numbers inside each cage must equal the value shown in its top-left corner.
Numbers cannot be repeated within the same cage.
Numbers cannot be repeated within the same row, column, or $3 \times 3$ region.

To find the correct solution, we have the following initial board:

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

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

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

Index sets

$\mathcal{I} = \{1, 2, \dots, 9\}$: Set of rows.

$\mathcal{J} = \{1, 2, \dots, 9\}$: Set of columns.

$\mathcal{K} = \{1, 2, \dots, 9\}$: Set of numerical values a cell can take.

$\mathcal{B} = \{1, 2, \dots, 9\}$: Set of $3 \times 3$ blocks or regions. Cells $(i,j)$ in block $b$ belong to subset $R_b$.

$\mathcal{C}$: Set of cages.

$\mathcal{S}_c$: Set of cells $(i,j)$ belonging to cage $c \in \mathcal{C}$.

$V_c$: Target value (sum) of cage $c \in \mathcal{C}$.

Decision variables

$x_{ijk} = 1$ if cell at row $i \in \mathcal{I}$ and column $j \in \mathcal{J}$ takes numerical value $k \in \mathcal{K}$, and $0$ otherwise.

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

Objective function
\[\min z = 0\]

We now define the rules of Classic Sudoku and those specific to the Killer variant as linear constraints:

Each cell must contain exactly one numerical value:
\[\displaystyle \sum_{k \in \mathcal{K}} x_{ijk} = 1 \quad \forall i \in \mathcal{I}, \; j \in \mathcal{J}\]

Each value must appear exactly once per row:
\[\displaystyle \sum_{j \in \mathcal{J}} x_{ijk} = 1 \quad \forall i \in \mathcal{I}, \; k \in \mathcal{K}\]

Each value must appear exactly once per column:
\[\displaystyle \sum_{i \in \mathcal{I}} x_{ijk} = 1 \quad \forall j \in \mathcal{J}, \; k \in \mathcal{K}\]

Each value must appear exactly once per $3 \times 3$ block:
\[\displaystyle \sum_{(i,j) \in R_b} x_{ijk} = 1 \quad \forall b \in \mathcal{B}, \; k \in \mathcal{K}\]

The sum of cell values in each cage must equal its target value:
\[\displaystyle \sum_{(i,j) \in \mathcal{S}_c} \sum_{k \in \mathcal{K}} k \cdot x_{ijk} = V_c \quad \forall c \in \mathcal{C}\]

Numbers cannot repeat within the same cage (although this is often implied by classic Sudoku rules for small cages, it is strictly part of the Killer rules):
\[\displaystyle \sum_{(i,j) \in \mathcal{S}_c} x_{ijk} \leqslant 1 \quad \forall c \in \mathcal{C}, \; k \in \mathcal{K}\]

Variable domains
\[x_{ijk} \in \{0, 1\} \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}, \; \forall k \in \mathcal{K}\]

Source code

The Python implementation of the optimization model (using libraries such as gurobipy or PuLP) for this post is available in the GitHub repository.

GitHub Repository: fjmartincampo/SudokuKiller

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

Killer Sudoku, the empty board challenge that math can solve

Formal description of the problem

Challenge solution

Source code

Enjoy Reading This Article?