**xor**condition in the model.

Assuming an \(n \times n\) board (with \(n\) even), we need to fill the cells \((i,j)\), with values 0 or 1, with the following restrictions:

- The number of ones in each row and in each column is equal to \(\displaystyle\frac{n}{2}\).
- Then we have also: The number of zeroes in each row and in each column is equal to \(\displaystyle\frac{n}{2}\).
- There can be no duplicate rows and no duplicate columns.
- In a row or column there cannot be more than two consecutive zeroes or ones.

A small example is given in (1):

Of course our central variable will be \(x_{i,j}\in\{0,1\}\). Condition 1 can be easily modeled using two constraints:

\[\begin{align} &\sum_j x_{i,j} = \frac{n}{2}\>\> \forall i\\ &\sum_i x_{i,j} = \frac{n}{2}\>\> \forall j \end{align}\] |

Condition 2 we don’t need to model explicitly: this follows from the above constraints.

Condition 3 (no duplicate rows or columns) is not very easy. One way to handle this, is to calculate a value for each row and column as follows:

\[\begin{align} &v_i = \sum_j 2^{j-1} x_{i,j}\\ &w_j = \sum_i 2^{i-1} x_{i,j} \end{align}\] |

and then make sure there are no duplicate \(v_i\)’s or duplicate \(w_j\)’s. This can be done using some all-different formulation (3). A big-M approach to implement \(v_i \le v_{i’}-1 \textbf{ or } v_i \ge v_{i’}+1, \forall i\ne i’\) can look like:

\[\begin{align} &v_i \le v_{i’}-1 + M \delta_{i,i’}\\ &v_i \ge v_{i’}+1 – M (1-\delta_{i,i’})\\ &\delta_{i,i’} \in \{0,1\} \end{align}\] |

However I want to attack this in a different way, using an **xor** condition (4). The constraints involved can be conceptualized as:

\[\begin{align} &\sum_j |x_{i,j} – x_{i’,j}| \ge 1 \>\> \forall i\ne i’\\ &\sum_i |x_{i,j} – x_{i,j’}| \ge 1 \>\> \forall j\ne j’ \end{align}\] |

The value \(z_{i,j,i’,j’}=|x_{i,j}-x_{i’,j’}|\) can be interpreted as \(z_{i,j,i’,j’}=x_{i,j} \textbf{ xor } x_{i’,j’}\): zero if \(x_{i,j}\) and \(x_{i’,j’}\) are identical and one if they are different. This in turn can be written as a set of inequalities (4):

\[\begin{align} &z_{i,j,i’,j’}\le x_{i,j} + x_{i’,j’}\\ &z_{i,j,i’,j’}\ge x_{i,j} - x_{i’,j’}\\ &z_{i,j,i’,j’}\ge x_{i’,j’} - x_{i,j}\\ &z_{i,j,i’,j’}\le 2 - x_{i,j} - x_{i’,j’}\\ &z_{i,j,i’,j’} \in \{0,1\} \end{align}\] |

After this we just need:

\[\begin{align} &\sum_j z_{i,j,i’,j} \ge 1 \>\> \forall i\ne i’\\ &\sum_i z_{i,j,i,j’} \ge 1 \>\> \forall j\ne j’ \end{align}\] |

Due to the nature of these conditions on \(z\) we can limit the **xor** constraints to

\[\begin{align} &z_{i,j,i’,j’}\le x_{i,j} + x_{i’,j’}\\ &z_{i,j,i’,j’}\le 2 - x_{i,j} - x_{i’,j’}\\ &z_{i,j,i’,j’} \in \{0,1\} \end{align}\] |

Note that we do not need to compute all \(z\) for all combinations \((i,j)\), \((i’,j’)\) (e.g. we never compare \(x_{2,3}\) with \(x_{3,2}\)). Furthermore we can relax \(z\) to be continuous between zero and one. Also note that if we compared row \(i\) and \(i’\) then we don’t need to compare row \(i’\) and row \(i\). Similarly for the columns. So we can do:

\[\begin{align} &\sum_j z_{i,j,i’,j} \ge 1 \>\> \forall i< i’\\ &\sum_i z_{i,j,i,j’} \ge 1 \>\> \forall j< j’ \end{align}\] |

Finally we need to handle restriction 4. This can be implemented as:

\[\begin{align} &1\le x_{i,j}+x_{i,j+1}+x_{i,j+2}\le 2\\ &1\le x_{i,j}+x_{i+1,j}+x_{i+2,j}\le 2 \end{align}\] |

Usually we need to write this as four inequalities (unless we can specify ranged equations). If the summation was longer I would have introduced extra variables with bounds one and two to reduce the number of constraints.

Note that the lower bound of one can also be inferred from \((1-x_{i,j})+(1-x_{i,j+1})+(1-x_{i,j+2})\le 2 \Rightarrow x_{i,j}+x_{i+1,j}+x_{i+2,j} \ge 1\).

##### Complete model

The variables are:

The dummy variable is related to a dummy objective: we look for a feasible integer solution only.

The different \(z\) values we need to compare is encoded in a set **compare**:

Finally the model equations are:

The result looks like:

---- 77 VARIABLE x.L i1 i2 i3 i4 i1 1 1 |

##### A large problem

The site (2) contains some “*very hard*” 14 x 14 puzzles. An example is:

It is interesting to see how this model behaves on this problem. It turns out the problem can be solved completely in preprocessing. E.g. Cplex and Gurobi report that zero Simplex iterations were needed and solve this problem blazingly fast:

Tried aggregator 3 times. Root node processing (before b&c): |

##### Verifying Uniqueness

A well-formed puzzle has only one solution. To verify whether a solution is unique we can use a similar strategy as in (6):

- First solve the model to obtain a solution \(x^*_{i,j}\).
- Formulate a constraint to forbid this solution.
- Add this constraint to the model and resolve. The solver should not find a new solution but rather report that this model is infeasible.

Here the cut can be formulated as:

\[\sum_{i,j} x^*_{i,j} x_{i,j} \le \frac{n^2}{2}-1\] |

##### Data Entry

Entering the problem data:

is an interesting issue. In GAMS “zero” and “does not exist” is identical, so we can **not** just use:

tableinit(i,j)

i1 i2 i3 i4

i1 1 0

i2 0

i3 0

i4 1 1 0

;

I used the following, which is not very clean:

tableinit(i,j)

i1 i2 i3 i4

i1 1 2

i2 2

i3 2

i4 1 1 2

;

x.fx(i,j)$(init(i,j)=1) = 1;

x.fx(i,j)$(init(i,j)=2) = 0;

Not sure if this is better:

parameterinit(i,j) / #i.#j NA /;

$onmultitableinit(i,j)

i1 i2 i3 i4

i1 1 0

i2 0

i3 0

i4 1 1 0

;variablex(i,j);

x.fx(i,j)$(init(i,j)<>NA) = init(i,j);

Note that AMPL has a "default" facility, so we can use in a data file:

param init default -1 : i1 i2 i3 i4 :=

i1 . 1 . 0

i2 . . 0 .

i3 . 0 . .

i4 1 1 . 0

;

It makes sense to use Excel for data entry. The initial configuration in Excel can look like:

To read this into GAMS and retain the zeros we can use the following code:

parameterinit(i,j);

$call 'gdxxrw i=takuzu.xlsx sq=n par=init rng=b3 rdim=1 cdim=1'

$oneps

$gdxin takuzu.gdx

$loaddc initdisplayinit;

The **Squeeze=no** option in the call to GDXXRW will tell it to retain the zeros. The **$OnEps** command tells GAMS to read the zero as an **EPS** special value. **EPS** is very useful: it is physically stored in the sparse data structures, but as soon as you do a numerical operation on it, it becomes zero. This will show:

---- 12 PARAMETER init i1 i2 i3 i4 i1 1.000 EPS |

This will now allow us to fix variables as:

binaryvariablex(i,j);

x.fx(i,j)$init(i,j) = init(i,j);

This model turned out to have quite a few interesting angles.

##### References

- Takuzu, https://en.wikipedia.org/wiki/Takuzu
- Online Takuzu puzzles, http://www.binarypuzzle.com/
- All-different and Mixed Integer Programming, http://yetanothermathprogrammingconsultant.blogspot.com/2016/05/all-different-and-mixed-integer.html
**xor**as Inequalities, http://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html- Similar puzzles are Sudoku and KenKen: http://yetanothermathprogrammingconsultant.blogspot.com/2016/10/mip-modeling-from-sudoku-to-kenken.html
- Unique Solutions in KenKen, http://yetanothermathprogrammingconsultant.blogspot.com/2016/12/unique-solutions-in-kenken.html

## No comments:

## Post a Comment