Sudoku Meets Linear Optimization

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.