## Thursday, March 26, 2020

### Special Sudoku (2)

In [1], a variant of Sudoku was discussed, where a side constraint is:

Orthogonally neigboring cells differ in value by at most 5

This max 5 difference is a convex constraint, so it can be expressed quite easily: $-5 \le v_{i,j} - v_{i',j'} \le 5$ for neighboring cells $$(i,j)$$ and $$(i',j')$$.

A more difficult restriction is: neighboring cells must differ by at least 2. Here is such a problem, again designed by Aad van de Wetering:

 Problem data

The rules are:
• Standard Sudoku-rules apply. cells in each row, column and sub-block have unique values from 1 through 9.
• In addition, neighboring (horizontal and vertical) cells have values that differ by 2 or more.
• Also, values 1 and 9 are considered to have a difference of 1. So neighboring cells, cannot have values 1 and 9.

I will try to solve this problem in two different ways. The first is an extension of what we did in [1]. The second one is a bit different.

#### Approach I

The constraint: neighbors must be different by at least two, can be formalized as $\left| v_{i,j} - v_{i',j'} \right| \ge 2$ for neighboring cells $$(i,j)$$ and $$(i',j')$$. The non-convexity of this constraint  \begin{align} & v_{i,j} - v_{i',j'} \ge 2 \\ & \mathbf{or} \\&v_{i,'j'} - v_{i,j} \ge 2 \end{align} requires extra binary variables and big-M constraints: \begin{align} & v_{i,j} - v_{i',j'} \ge 2 - M\cdot \delta_{i,j,i',j'} \\ & v_{i,'j'} - v_{i,j} \ge 2 - M\cdot (1-\delta_{i,j,i',j'})\\ & \delta_{i,j,i',j'} \in \{0,1\}\end{align} So, how large should $$M$$ be? The maximum difference between two different values is 8. So we need $$2-M\le -8$$ or $$M=10$$.

We ignored that values 1 and 9 also have a difference of 1. As all other combinations are allowed, we can handle this by $\left|v_{i,j}-v_{i',j'}\right| \le 7$ This is a constraint we already know how to handle: $-7 \le v_{i,j}-v_{i',j'} \le 7$ Interestingly, this addition restriction also can help us in tightening our big-M value. We can now use $$M = 9$$. Note that with this smaller big-M we still need this constraint: the big-M constraint only covers one of the needed two sides of this constraint.

The complete model can look like:

Mixed-Integer Programming Model I
\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}\\ & \color{darkred}v_{i,j} - \color{darkred}v_{i',j'} \ge 2 - \color{darkblue}M\cdot \color{darkred}\delta_{i,j,i',j'}&&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} &&\text{Min difference of 2} \\ & \color{darkred}v_{i,'j'} - \color{darkred}v_{i,j} \ge 2 - \color{darkblue}M\cdot (1-\color{darkred}\delta_{i,j,i',j'}) &&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'}\\ & -7 \le \color{darkred}v_{i,j} - \color{darkred}v_{i',j'} \le 7 &&\forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} && \text{Neighbors differ by max 7} \\ & \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\} \\ & \color{darkred}\delta_{i,j,i',j'} \in \{0,1\} \\ & \color{darkblue}M = 9\end{align}

Notes:

• This model solves quickly: the presolve can remove all rows and columns.
• The solution is unique (see [1]).
• Using the above data set we actually can drop the "max 7" constraint. I think that is just a property of this data set. In general, we should include this constraint.

#### Approach II

A simpler approach is to consider the pairs of values that cannot be neighbors: $(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,1)$ We also need to add their symmetrical counterparts $(2,1),(3,2),\dots$ Detail: this is due to the way we organized the neighbors. The neighbor set did not have both: i.e. cells $$\text{(1,2)-(1,3)}$$ are neighbors, so this is stored. But, I did not also store the combination $$\text{(1,3)-(1,2)}$$.

After automatically generating the combinations $$(k,k')$$ that we need to prevent, the forbid data can look like:

----     55 SET forbid  combinations of values we want to exclude

v1          v2          v3          v4          v5          v6          v7          v8          v9

v1                     YES                                                                                 YES
v2         YES                     YES
v3                     YES                     YES
v4                                 YES                     YES
v5                                             YES                     YES
v6                                                         YES                     YES
v7                                                                     YES                     YES
v8                                                                                 YES                     YES
v9         YES                                                                                 YES


This table contains elements $$\mathit{forbid}_{k,k'}$$ we want to forbid. Note that we can exclude the diagonal from this: neighboring cells already cannot have the same value. For this set of value-pairs, we want to add the constraint:$x_{i,j,k} + x_{i',j',k'} \le 1$ for all neighboring cells $$(i,j)$$ and $$(i',j')$$ and for all forbidden value combinations $$(k,k')$$. We have 18 of these combinations and 144 neighbors to check, yielding 2592 of these constraints.

The full model can look like:

Mixed-Integer Programming Model II
\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} + \color{darkred}x_{i',j',k'} \le 1 && \begin{aligned}& \forall i,j,i',j'|\color{darkblue}{nb}_{i,j,i',j'} \\ & \forall k,k'|\color{darkblue}{\mathit{forbid}}_{k,k'} \end{aligned}&&\text{Forbid combinations} \\ & \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}

When we run this model, we will see the solution:

----     84 PARAMETER v  values (postprocessing)

c1          c2          c3          c4          c5          c6          c7          c8          c9

r1           9           2           6           4           1           7           3           5           8
r2           3           5           8           2           6           9           7           1           4
r3           1           7           4           8           3           5           2           6           9
r4           7           4           1           6           9           2           5           8           3
r5           5           8           3           1           7           4           9           2           6
r6           2           6           9           3           5           8           4           7           1
r7           6           9           2           5           8           3           1           4           7
r8           8           3           5           7           4           1           6           9           2
r9           4           1           7           9           2           6           8           3           5


This solution is unique. The presolver completely solves the model, so no actual iterations are performed.