Sudoku Meets Linear Optimization

Sudoku is a logic-based number puzzle played on a $9 \times 9$ grid, divided into nine smaller $3 \times 3$ blocks. The goal is to fill the grid with digits from $1$ to $9$ in such a way that each number appears exactly once in every row, column, and block.

The modern version of Sudoku was popularized in the late 1980s by the Japanese puzzle company Nikoli, although its roots go back earlier to a puzzle called “Number Place” published in the United States in 1979. Interestingly, the name “Sudoku” is an abbreviation of the Japanese phrase “Sūji wa dokushin ni kagiru”, which means “the digits must be single” or “the digits must occur only once”. Sudoku puzzles have since become a global phenomenon, appearing in newspapers, books, and apps, and they are enjoyed by millions for their combination of logic, pattern recognition, and problem-solving.

A valid Sudoku puzzle starts with some cells already filled, and the player must deduce the remaining numbers using logical reasoning, rather than guessing. For instance, consider the following Sudoku:

This Sudoku can be solved as follows:

To model Sudoku as a binary linear optimization problem, we need to first define all the components of the model.

Sets of indices

• \(\mathcal{R}\): Rows of the board.
• \(\mathcal{C}\): Columns of the board.
• \(\mathcal{N}\): Numbers used in the puzzle.

Parameters

• \(A_{rc}\): Matrix representing the initial Sudoku board (with missing values set to 0).

Decision variables

• \(x_{rcn} = 1\) if number $n$ is placed in row $r$ and column $c$, and $0$ otherwise.

In Sudoku, each puzzle typically has a unique solution (or if multiple solutions exist, all of them satisfy the same Sudoku rules). Therefore, the objective function is not critical here. For the purpose of modeling, it is sufficient to minimize a constant ($L$):

Objective function

• \[\min z = L\]

Next, we define the constraints that enforce the rules of Sudoku.

Each cell must contain exactly one number:

• \[\displaystyle \sum_{n \in \mathcal{N}} x_{rcn} = 1 \quad \forall r \in \mathcal{R}, c \in \mathcal{C}\]

Each number must appear exactly once in each row:

• \[\displaystyle \sum_{r \in \mathcal{R}} x_{rcn} = 1 \quad \forall c \in \mathcal{C}, n \in \mathcal{N}\]

Each number must appear exactly once in each column:

• \[\displaystyle \sum_{c \in \mathcal{C}} x_{rcn} = 1 \quad \forall r \in \mathcal{R}, n \in \mathcal{N}\]

Each number must appear exactly once in each $3 \times 3$ block:

• \[\displaystyle \sum_{r=3p-2}^{3p} \sum_{c=3q-2}^{3q} x_{rcn} = 1 \quad \forall n \in \mathcal{N}, \; p,q \in \{1,2,3\}\]

Finally, we define the domain of the decision variables:

Variables’ domain

• \[x_{rcn} \in \{0,1\} \quad \forall r \in \mathcal{R}, c \in \mathcal{C}, n \in \mathcal{N}\]

Notes for readers:

• This formulation allows you to solve Sudoku puzzles using standard binary linear programming optimizers such as Gurobi or CPLEX.
• While this approach is more mathematical than typical human-solving methods, it demonstrates the power of optimization modelling in combinatorial problems.