Sudoku Meets Linear Optimization

Image by Bozhin Karaivanov from Unsplash

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:

Do you dare to solve it logically before taking on the model?

The Sudoku can be formulated as a binary optimization model. Do you dare to try it?

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), $\forall r \in \mathcal{R}, \; \forall c \in \mathcal{C}$.

Decision variables

$x_{rcn} = 1$ if number $n \in \mathcal{N}$ is placed in row $r \in \mathcal{R}$ and column $c \in \mathcal{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}, \; \forall 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}, \; \forall 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}, \; \forall 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}, \; \forall 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}, \; \forall c \in \mathcal{C}, \; \forall n \in \mathcal{N}\]

Source Code

The complete Python implementation of the optimization model presented in this post, together with the Sudoku instance shown above, is available in the project’s GitHub repository.

GitHub repository: fjmartincampo/Sudoku

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

Solution to the challenge

Source Code

Enjoy Reading This Article?