# How to do one octomino?

Here are all the 369 octominoes: https://en.wikipedia.org/wiki/Octomino

If I have an 8x8 area, how to create one octomino, any of those 369 and any rotation and mirroring is allowed?

I have tried several linearized and/or tricks but those produced sometimes correct sometimes wrong solutions. How to make constraints so the eight binary ones are always connected?

You want to model a connected subgraph, with $$8$$ nodes, of an $$8 \times 8$$ grid graph. Let binary decision variable $$x_{ij}$$ indicate whether undirected edge $$\{i,j\}\in E$$ is selected. Let binary decision variable $$y_i$$ indicate whether node $$i$$ is selected. Let binary decision variable $$s_i$$ indicate whether node $$i$$ is selected as the source node. Let nonnegative decision variable $$f_{ij}$$ be the flow across directed arc $$(i,j)\in A$$. The idea is to enforce connectivity by sending one unit of flow from the source to each other selected node. The constraints are: \begin{align} \sum_i y_i &= 8 \tag1\label1 \\ x_{ij} &\le y_i &&\text{for all \{i,j\}\in E} \tag2\label2 \\ x_{ij} &\le y_j &&\text{for all \{i,j\}\in E} \tag3\label3 \\ x_{ij} &\ge y_i + y_j - 1 &&\text{for all \{i,j\}\in E} \tag4\label4 \\ \sum_i s_i &= 1 \tag5\label5 \\ s_i &\le y_i && \text{for all i} \tag6\label6 \\ f_{ij} + f_{ji} &\le 7 x_{ij} && \text{for all \{i,j\}\in E} \tag7\label7 \\ \sum_{(i,j) \in A} f_{ij} - \sum_{(j,i)\in A} f_{ji} &= 8 s_i - y_i &&\text{for all i} \tag8\label8 \end{align} Constraint \eqref{1} selects $$8$$ nodes. Constraints \eqref{2} through \eqref{4} link the node variables to the edge variables. Constraint \eqref{5} selects one source node. Constraint \eqref{6} forces the source node to be a selected node. Constraint \eqref{7} allows flow only on selected edges. Constraint \eqref{8} enforces flow balance.
Because a connected graph must have at most one more node than the number of edges, an optional constraint is $$\sum_{\{i,j\}\in E} x_{ij} \ge 7.$$
Note that you can relax $$x$$ to be nonnegative because it will automatically take values in $$\{0,1\}$$ if $$y$$ does.
• $|E|=8\times7\times2$ and $|A|=2|E|$ Aug 5, 2023 at 19:34