This is the thirtieth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hello! Today we are going to solve Sudoku using ILP.

Description

In Sudoku we need to fill 9 \times 9 grid with numbers. In every column, in every row, and in nine smaller subgrids we can use every number from 1 to 9 exactly once. We usually start with few fields filled and we need to find the rest. See the picture below (from wikipedia):
Sudoku

In this post we will use basic set operations a lot so make sure that you understand them.

Variables

Let’s start with variables for the problem. We usually use binary variables to indicate decision, however, this time we will use integer variables in range [1; 9] to represent the solutions. It is quite intuitive: after solving the problem we obtain the result by checking the value of variable for given board field. So we define the following variables:

    \begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le 9}\displaystyle\mathop{\forall}_{1 \le j \le 9} v_{i,j} \end{gather*}

We also make sure that they are in the correct range:

    \begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le 9}\displaystyle\mathop{\forall}_{1 \le j \le 9} 1 \le v_{i,j} \le 9 \end{gather*}

Let’s now define constraints.

Constraints

This part is very easy. We already know how to define “all different” constraint, so all we need to do is to add constraints for every row, every column, and every subgrid:

    \begin{gather*} \displaystyle\mathop{\forall}_{1 \le i \le 9} \text{ AllDifferent}\left( v_{i, 1}, v_{i, 2}, \ldots, v_{i, 9} \right) \\ \displaystyle\mathop{\forall}_{1 \le j \le 9} \text{ AllDifferent}\left( v_{1, j}, v_{2, j}, \ldots, v_{9, j} \right) \\ \displaystyle\mathop{\forall}_{0 \le x \le 2} \displaystyle\mathop{\forall}_{0 \le y \le 2} \text{ AllDifferent}\left( v_{3x+1, 3y+1}, \ldots,  v_{3x+3, 3y+3} \right) \end{gather*}

Summary

As we can see, our toolkit for building ILP formulas is quite powerfull and we are able to solve Sudoku almost instantly just by translating rules of the game (nine different numbers in each column, nine different numbers in each row, nine different numbers in each subgrid) to mathematical operators.