Problem |

- Each cell has an integer value between 1 and 9
- In each row, column and sub-block cells must be unique
- Some cells have a predefined value

In addition, we have the following restriction:

- The maximum difference between the value of two neighboring cells (orthogonal, that is horizontal or vertical) is 5

To solve this you can follow this video [1]:

Of course, we want to try to solve this as a Mixed-Integer Programming model.

#### Review: a linear integer programming model for standard Sudoku

When we want to solve Sudokus, the easiest approach is to define the following binary decision variables [2]: \[x_{i,j,k} = \begin{cases} 1 & \text{if cell $(i,j)$ has value $k$} \\ 0 & \text{otherwise}\end{cases}\] Here \(k \in \{1,\dots,9\}\). We have 27 areas we need to check for unique values: rows, columns and sub-blocks. We can organize this as a set: \[u_{a,i,j}\>\text{exists if and only if area $a$ contains cell $(i,j)$}\] This is data. We also have a set of given cells, which we can fix. The resultimg MIP model can look like [2]:

Mixed-Integer Programming Model for standard Sudoku |
---|

\[\begin{align}\min\>& 0 && && \text{Dummy objective}\\ & \sum_k \color{darkred}x_{i,j,k} = 1 &&\forall i,j && \text{One $k$ in each cell}\\ & \sum_{i,j|\color{darkblue}u_{a,i,j}} \color{darkred}x_{i,j,k} = 1 && \forall a,k && \text{Unique values in each area}\\ & \color{darkred}x_{i,j,k} = 1 && \text{where } k=\color{darkblue}{\mathit{Given}}_{i,j} &&\text{Fix given values}\\ &\color{darkred}x_{i,j,k} \in \{0,1\} \end{align}\] |

#### Linear integer programming model for Sudoku variant

alias
(i,ii),(j,jj);setnb(i,j,ii,jj) 'neighbors'; nb(i,j,i-1,j) = yes;nb(i,j,i,j-1) = yes; |

We can introduce the post-processing step directly into the MIP and then enforce our difference constraint on the variables \(v_{i,j}\). This can look like \[\begin{align} & v_{i,j} = \sum_k k \cdot x_{i,j,k} && \text{cell values as constraint} \\ & -5 \le v_{i,j} - v_{i',j'} \le 5 && \text{for neigboring cells $(i,j)$ and $(i',j')$}\end{align}\]

With this, we can formulate:

Mixed-Integer Programming Model for Sudoku Variant |
---|

\[\begin{align}\min\>& 0 && && \text{Dummy objective}\\ & \sum_k \color{darkred}x_{i,j,k} = 1 &&\forall i,j && \text{One $k$ in each cell}\\ & \sum_{i,j|\color{darkblue}u_{a,i,j}} \color{darkred}x_{i,j,k} = 1 && \forall a,k && \text{Unique values in each area}\\ &\color{darkred}v_{i,j} =\sum_k \color{darkblue}k\cdot\color{darkred}x_{i,j,k} && \forall i,j &&\text{Value of cell}\\ & -5 \le \color{darkred}v_{i,j} - \color{darkred}v_{i',j'} \le 5 &&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} && \text{Neighbors differ by max 5} \\ & \color{darkred}x_{i,j,k} = 1 && \text{where } k=\color{darkblue}{\mathit{Given}}_{i,j} &&\text{Fix given values}\\&\color{darkred}x_{i,j,k} \in \{0,1\} \\ &\color{darkred}v_{i,j} \in \{1,\dots,9\} \end{align}\] |

This model solves very easily. The presolver can solve this model completely, so we don't even have to start the branch-and-bound phase. As a result, we can make a much shorter movie:

The solution of this model looks like:

---- 80 VARIABLE v.L value of each cell c1 c2 c3 c4 c5 c6 c7 c8 c9 r1 2 4 9 6 7 5 8 3 1 r2 3 8 5 1 4 9 6 7 2 r3 7 6 1 2 3 8 9 5 4 r4 8 9 6 3 1 4 5 2 7 r5 5 7 3 8 6 2 1 4 9 r6 1 2 4 5 9 7 3 8 6 r7 6 1 2 4 8 3 7 9 5 r8 4 3 7 9 5 1 2 6 8 r9 9 5 8 7 2 6 4 1 3

#### Unique solution

A proper Sudoku puzzle has one unique solution. We can verify this by adding a cut to the problem after solving it. The cut should forbid the current solution (and allow all other solutions). In this case, the cut can look like \[\sum_{i,j,k} x^*_{i,j,k} x_{i,j,k}\le 9^2-1\] where \(x^*\) is the previously found solution. Indeed, this puzzle has a single, unique solution: after adding the cut, the problem becomes (integer) infeasible.

#### References

- A Sudoku With Just 11 Digits = Dutch Genius!, https://www.youtube.com/watch?v=ZU5fSDHJq8k
- MIP Modeling: from Sudoku to KenKen via Logarithms, https://yetanothermathprogrammingconsultant.blogspot.com/2016/10/mip-modeling-from-sudoku-to-kenken.html

## No comments:

## Post a Comment