Dominosa, Beyond Dominoes

Image by Mick Haupt from Unsplash

Dominosa is a fascinating logic game created by O.S. Adler in the late 19th century. Although placing domino tiles on a grid might seem simple at first glance, reconstructing the original layout of a complete domino set from a grid of revealed numbers poses a true combinatorial challenge.

The objective is to cover a rectangular board consisting of $R \times C$ numbered cells using a complete set of dominoes (from double zero $[0,0]$ to double $M$, $[M,M]$), such that each cell is covered by exactly half of a tile whose values match the numbers printed on the board.

Formal Problem Description

Given a complete set of domino tiles up to a maximum value $M$ (containing $N_d = \frac{(M+1)(M+2)}{2}$ tiles) and an $R \times C$ grid of numbers with $R \times C = 2 \cdot N_d = (M+1)(M+2)$ cells, we must place all tiles respecting the following rules:

Unique tile usage: Each tile $[u, v]$ from the complete set (with $0 \leqslant u \leqslant v \leqslant M$) must be used exactly once.
Complete, non-overlapping coverage: Each cell on the board must be covered by half of a single domino tile, leaving no empty spaces or overlapping tiles.
Physical adjacency: A domino tile occupies exactly two adjacent cells on the board, either horizontally or vertically.
Value matching: The two numbers on a domino placed over a pair of adjacent cells must match the values printed on those cells.

The key question we need to answer is: Does a valid placement of the complete domino set exist that perfectly covers the board, and how can we find it automatically?

Consider the following example (using tiles from 0 to 9 on a $10 \times 11$ board):

Do you dare to solve it logically before taking on the model?

This logic puzzle can be formulated elegantly and systematically as a Binary Linear Programming problem. Dare to try it?

To model Dominosa as a binary linear programming problem, we identify all potential positions where a tile could be placed (adjacent edges on the board) and link each position to its corresponding domino tile based on the values of its cells.

Index Sets

$\mathcal{I} = \{1, 2, \dots, R\}$: Board rows.

$\mathcal{J} = \{1, 2, \dots, C\}$: Board columns.

$\mathcal{M} = \{0, 1, \dots, M\}$: Possible numerical values of the domino tiles.

$\mathcal{D} = \{[u, v] \in \mathcal{M} \times \mathcal{M} : u \leqslant v\}$: Set of tiles in the complete domino set (avoiding duplicates due to symmetry).

$\mathcal{E} = \{ ((i,j), (r,c)) \in (\mathcal{I} \times \mathcal{J})^2 : |i-r| + |j-c| = 1, \; (i,j) < (r,c) \}$: Set of ordered pairs of adjacent cells on the board, under lexicographical order $(i,j) < (r,c) \iff i < r \lor (i = r \land j < c)$.

$\mathcal{E}_{uv} = \{ ((i,j), (r,c)) \in \mathcal{E} : \{V_{ij}, V_{rc}\} = \{u, v\} \}$: Set of board positions whose numerical values match tile $[u,v]$.

Parameters

$V_{ij} \in \mathcal{M}$: Number printed on cell $(i,j)$ of the board.

$R, C$: Number of rows and columns of the board, where $R \times C = 2 \cdot N_d = (M+1)(M+2)$.

Decision Variables

$x_{ijrc} = 1$ if a domino tile is placed on the adjacent edge $((i,j), (r,c)) \in \mathcal{E}$, and $0$ otherwise.

Since this is a feasibility problem (finding any configuration that satisfies all game rules), the objective function is arbitrary:

Objective Function
\[\min z = 0\]

We formulate the rules of Dominosa as linear constraints:

Exact coverage per cell:

Each cell $(i,j)$ on the board must be covered by exactly one domino tile (summing edges where the cell is either the first or second element of the ordered pair):
\[\sum_{(r,c) : ((i,j),(r,c)) \in \mathcal{E}} x_{ijrc} + \sum_{(r,c) : ((r,c),(i,j)) \in \mathcal{E}} x_{rcij} = 1 \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Unique use of each domino tile:

Each tile $[u,v] \in \mathcal{D}$ from the complete set must be placed in exactly one of the valid positions on the board where its numbers match:
\[\sum_{((i,j), (r,c)) \in \mathcal{E}_{uv}} x_{ijrc} = 1 \quad \forall [u,v] \in \mathcal{D}\]

Variable Domain
\[x_{ijrc} \in \{0, 1\} \quad \forall ((i,j), (r,c)) \in \mathcal{E}\]

Source Code

The implementation in Python using the Gurobipy library to solve this optimization problem is available on the GitHub repository.

GitHub Repository: fjmartincampo/Dominosa

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.

Formal Problem Description

Puzzle Solution

Source Code

Enjoy Reading This Article?