Integer programming formulation of Takuzu

Question

A Takuzu is a logic-based number puzzle whose objective is to fill a (usually $10 \times 10$) grid with ones and zeros such that the following conditions are satisfied:

1. Each row and each column have an equal number of ones and zeros.

2. Each row and each column have a maximum of $2$ equal adjacent numbers.

3. All rows are different and all columns are different (but a row can be the same as a column).

I am interested in an integer programming (IP) formulation to solve such a puzzle. Denote $A$ as the $2n \times 2n$ matrix representing the grid of such a puzzle (let's assume a square grid) and let $\mathcal{N} = \{1,\ldots,2n\}$ . The IP formulation is then given by

\begin{align} \min 1 \\ \text{s.t.} \quad \sum_{j \in \mathcal{N}}a_{ij} & = n \quad \forall \ i \in \mathcal{N} \tag{1.1} \\ \sum_{i \in \mathcal{N}}a_{ij} & = n \quad \forall \ j \in \mathcal{N} \tag{1.2} \\ \sum_{j \in \mathcal{N}} |a_{ij}-a_{kj}| & \geq 1 \quad \forall \ i \in \mathcal{N}, \forall \ k \in \mathcal{N}, i \neq k \tag{3.1} \\ \sum_{i \in \mathcal{N}} |a_{ij}-a_{ik}| & \geq 1 \quad \forall \ j \in \mathcal{N}, \forall \ k \in \mathcal{N}, j \neq k \tag{3.2} \\ a_{ij} & \in \mathbb{B} \quad \forall \ i \in \mathcal{N}, \forall \ j \in \mathcal{N} \end{align}

I have two main questions:

1: Is the formulation valid? Any tips regarding notation or solvability?

2: How do I enforce the 2nd condition in my program?

Answer 1

Encoding your second constraint can be done for rows with :

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N} \setminus \{1,2 n\}, 1 \leq a_{i,j-1} + a_{i,j} + a_{i,j+1} \leq 2$

The rest of your formulation is valid.

What I have to tell you then won't make you happy : solving this by branch-and-bound will suck. You have a huge symmetry in this integer programming formulation, and this is very bad. You will probably have some results with a good solver, but for a larger $n$, I think using constraint programming would work better.

Following comment : here is a way to linearise $(3.1)$ (without using the objective function) :

define $\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k}$ the boolean equal to $|a_{i,j}-a_{k,j}|$. In order for $b$ to be properly defined, you can add the constraints

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \leq a_{i,j} + a_{k,j} $

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \leq 2 - (a_{i,j} + a_{k,j}) $

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \geq a_{i,j} - a_{k,j} $

$\forall i \in \mathcal{N}, \forall j \in \mathcal{N}, \forall k \in \mathcal{N}, b_{i,j,k} \geq a_{k,j} - a_{i,j} $

Then express $(3.1)$ :

$\forall i \in \mathcal{N}, \forall k \in \mathcal{N}, \sum_{j \in \mathcal{N}} b_{i,j,k} \geq 1 $