1. Introduction#

Sudoku, originally called Number Place, is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a $9×9$ grid with digits so that each column, each row, and each of the nine $3×3$ subgrids that compose the grid (also called "boxes", "blocks", or "regions") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Source: Wikipedia

2. Modeling the puzzle#

Some symbols used in this problem

• $n$ is a perfect square representing the size of the grid.
• $F$ is the set of pairs $(i, j)$ representing the coordinates of the pre-filled cells in the grid.
• $V_{ij}$ is the number filled in the cell $(i, j) \in F$
• $B_b$ is the set of cells $(i, j)$ in the $b$-th block($0 \leq b < n$).

2.1. Decision variables#

For each cell $(i, j)$ in the grid and a number $k$, we define a variable $x(i,j,k)$ such that

$$x(i, j, k) = \begin{cases} 1 & \text{ if cell } (i, j)\text{ contains } {k} \\ 0 & \text{ otherwise } \end{cases}$$

2.2. Constraints#

• Each cell contains only one number.

$$\sum\limits_{k = 1}^{n}{x(i, j, k)} = 1, \\ \forall 0 \leq i, j < n$$

• Each row contains all numbers from 1 to $n$

$$\sum\limits_{j = 0}^{n - 1}{x(i, j, k)} = 1, \\ \forall 0 \leq i < n, 1 \leq k \leq n$$

• Each column contains all numbers from 1 to $n$

$$\sum\limits_{i = 0}^{n - 1}{x(i, j, k)} = 1, \\ \forall 0 \leq j < n, 1 \leq k \leq n$$

• Each block contains all numbers from 1 to $n$

$$\sum\limits_{(i, j) \in B_b}{x(i, j, k)} = 1, \\ \forall 0 \leq b < n, 1 \leq k \leq n$$

• Pre-filled cells

$$x(i, j, V_{ij}) = 1, \\ \forall (i, j) \in F$$

2.3. Objective function#

This problem does not have an objective function, as we are not aiming to minimize or maximize any value. Our goal is simply to find a feasible solution. Technically, when programming, we can set the objective function to a constant (I often choose 0)

3. Conclusion#

Sudoku is one of the fundamental exercises for mastering modeling skills. When I first started learning modeling, I was very impressed by the idea of using a three-dimensional binary variable for this problem. All the remaining constraints of the problem were modeled very easily with this variable assignment. This is also a common technique used in modeling, and we will encounter these binary variables again in future articles of this series.

For more Sudoku puzzles and variations, please refer to Krazydad. The Python code for Sudoku modeling is available at Tung-hehe

Happy modeling!