1. Introduction#

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

• The grid is completely covered by $X$, $O$ and $I$
• 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$, $O$, and $I$ is equal.

Below is an example of a 12×12 Troix puzzle and its solution.

2. Modeling puzzle#

• $n_R$ is the number of rows in the grid ($n_R$ is a multiple of 3)
• $n_C$ is the number of columns in the grid ($n_C$ is a multiple of 3)
• $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$
• $F_I$ is the set of all cells $(i, j)$ already filled with $I$

2.1. Decision variables#

For each cell $(i, j)$ in the grid, we define variables $x(i, j)$, $y(i, j)$, $z(i, j)$ such that

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

2.2. Constraints#

• Cells already filled

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

• The grid is completely covered by $X$, $O$ and $I$

$$x(i, j) + y(i, j) + z(i, j) = 1, \\ \forall 0 \leq i < n_R, 0 \leq j < n_C$$

• 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 \\ y(i, j) + y(i, j + 1) + y(i, j + 2) \leq 2 \\ z(i, j) + z(i, j + 1) + z(i, j + 2) \leq 2 \\ \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 \\ y(i, j) + y(i + 1, j) + y(i + 2, j) \leq 2 \\ z(i, j) + z(i + 1, j) + z(i + 2, j) \leq 2 \\ \end{cases} \\ \forall 0 \leq i < n_R - 2, 0 \leq j < n_C$$

• In each row, the number of $X$, $O$, and $I$ is equal.

$$\begin{cases} \sum\limits_{j = 0}^{n_C - 1}{x(i, j)} = {n_C \over 3} \\ \sum\limits_{j = 0}^{n_C - 1}{y(i, j)} = {n_C \over 3} \\ \sum\limits_{j = 0}^{n_C - 1}{z(i, j)} = {n_C \over 3} \\ \end{cases} \\ \forall 0 \leq i < n_R$$

• In each column, the number of $X$, $O$, and $I$ is equal.

$$\begin{cases} \sum\limits_{i = 0}^{n_R - 1}{x(i, j)} = {n_R \over 3} \\ \sum\limits_{i = 0}^{n_R - 1}{y(i, j)} = {n_R \over 3} \\ \sum\limits_{i = 0}^{n_R - 1}{z(i, j)} = {n_R \over 3} \\ \end{cases} \\ \forall 0 \leq j < n_C$$

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#

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

Happy modeling!