1. Introduction#

Binox is a logic puzzle described as follows: given a grid of squares with some cells already filled with $X$ or $O$. Player needs to complete the grid by filling in the empty cells with $X$ or $O$, satisfying the following conditions:

• The grid is completely covered by $X$ and $O$
• In each row/column, there is no sequence of more than 2 consecutive cells filled with the same symbol
• In each row/column, the number of $X$ is equal to the number of $O$
• Each row/column is unique (No two rows are the same, and no two columns are the same)

Below is an example of a 6×6 Binox puzzle and its solution.

2. Modeling the puzzle#

• $n_R$ is the number of rows in the grid ($n_R$ is an even number)
• $n_C$ is the number of columns in the grid ($n_C$ is an even number)
• $F_X$ is the set of all cells $(i, j)$ already filled with $X$
• $F_O$ is the set of all cells $(i, j)$ already filled with $O$

2.1. Decision variables#

For each cell $(i, j)$ in the grid, we define a variable $x(i, j)$ such that

$$x(i, j) = \begin{cases} 1 & \text{if cell } (i, j) \text{ filled with X } \\ 0 & \text{if cell } (i, j) \text{ filled with O } \end{cases}$$

2.2. Constraints#

• Cells already filled

$$\begin{cases} x(i, j) = 1, \forall (i, j) \in F_X\\ x(i, j) = 0, \forall (i, j) \in F_O \end{cases}$$

• In each row, there is no sequence of more than 2 consecutive cells filled with the same symbol

$$\begin{cases} x(i, j) + x(i, j + 1) + x(i, j + 2) \leq 2 \\ x(i, j) + x(i, j + 1) + x(i, j + 2) \geq 1 \end{cases} \\ \forall 0 \leq i < n_R, 0 \leq j < n_C - 2$$

• In each column, there is no sequence of more than 2 consecutive cells filled with the same symbol

$$\begin{cases} x(i, j) + x(i + 1, j) + x(i + 2, j) \leq 2 \\ x(i, j) + x(i + 1, j) + x(i + 2, j) \geq 1 \end{cases} \\ \forall 0 \leq i < n_R - 2, 0 \leq j < n_C$$

• In each row, the number of $X$ is equal to the number of $O$

$$\sum\limits_{j = 0}^{n_C - 1}{x(i, j)} = {n_C \over 2}, \\ \forall 0 \leq i < n_R$$

• In each column, the number of $X$ is equal to the number of $O$

$$\sum\limits_{i = 0}^{n_R - 1}{x(i, j)} = {n_R \over 2}, \\ \forall 0 \leq j < n_C$$

• Each row is unique. To linearize this constraint, we can rephrase it as follows: for any two rows $i$ and $j$, there exists at least one position $k$ such that $x(i, k) \ne x(j, k)$.

  For any two distinct rows $i \ne j$, and for each column k, we define an intermediate variable y(i, j, k) such that

  $$y(i, j, k) = \begin{cases} 1 & \text{if } x(i, k) = x(j, k) \\ 0 & \text{otherwise} \end{cases}$$

  Using geometric method we can represent the variables $y$ through the variables $x$ by the following constraints:

  $$\begin{cases} y(i, j, k) + x(i, k) + x(j, k) \geq 1 \\ y(i, j, k) + x(i, k) \leq x(j, k) + 1 \\ y(i, j, k) + x(j, k) \leq x(i, k) + 1 \\ x(i, k) + x(j, k) \leq y(i, j, k) + 1 \end{cases} \\ \forall 0 \leq i, j < n_R, i \ne j, 0 \leq k < n_C$$

  We linearize the original constraint using the variables $y$ as follows

  $$\sum\limits_{k = 0}^{n_C - 1}{y(i, j, k)} \leq n_C - 1, \\ \forall 0 \leq i, j < n_R, i \ne j$$

• Each column is unique. Similarly to the above condition, for any two distinct columns $i$ and $j$, and for each row $k$, we construct an intermediate variable $z(i, j, k)$ such that

  $$z(i, j, k) = \begin{cases} 1 & \text{if } x(k, i) = x(k, j) \\ 0 & \text{otherwise} \end{cases}$$

  Represent the variables $z$ through the variables $x$ by the following constraints:

  $$\begin{cases} z(i, j, k) + x(k, i) + x(k, j) \geq 1 \\ z(i, j, k) + x(k, i) \leq x(k, j) + 1 \\ z(i, j, k) + x(k, j) \leq x(k, i) + 1 \\ x(k, i) + x(k, j) \leq z(i, j, k) + 1 \end{cases} \\ \forall 0 \leq k < n_R, 0 \leq i, j < n_C, i \ne j$$

  Linearize the original constraint as follows

  $$\sum\limits_{k = 0}^{n_R - 1}{z(i, j, k)} \leq n_R - 1, \\ \forall 0 \leq i, j < n_C, i \ne j$$

2.3. Objective function#

This problem does not have an objective function, as we are not aiming to minimize or maximize any value. Our goal is simply to find a feasible solution. Technically, when programming, we can set the objective function to a constant (I often choose 0)

3. Conclusion#

The highlight of this puzzle is the unique row/column constraint. In reality, such constraints are often very difficult to model efficiently. Imagine if we had thousands of rows or columns; the number of constraints would be enormous. In such cases, we must find alternative ways to solve the problem effectively

For more Binox puzzles and variations, please refer to Krazydad. The Python code for Binox modeling is available at Tung-hehe

Happy modeling!