TAOCP 7.2.2.1 Exercise 71

Exercise 71. [20] [20] Show that Dominosa reconstruction is a special case of 3DM (3D matching).

Verified: no
Solve time: 1m04s

Solution

Let the Dominosa instance consist of a $7\times 8$ grid of cells $C$, each cell $x\in C$ carrying a label $\lambda(x)\in{0,1,\dots,6}$. Let $D$ be the set of domino types, so

$D={{i,j}\mid 0\le i\le j\le 6}.$

Each valid placement pairs each domino type exactly once with an unordered pair of orthogonally adjacent cells whose labels are exactly that type.

Construct a 3-dimensional matching instance $(X,Y,Z,\mathcal{T})$ as follows. Let

$X=C,\qquad Y=C,\qquad Z=D.$

Each triple in $\mathcal{T}$ corresponds to placing a domino on an adjacent pair of cells with matching labels. For each unordered adjacent pair ${u,v}$ of cells in the grid and for each orientation $(u,v)$ and $(v,u)$, include the triple $(u,v,t)$ in $\mathcal{T}$ if and only if

$t={\lambda(u),\lambda(v)}.$

Thus $(u,v,t)\in \mathcal{T}$ exactly when $u$ and $v$ are adjacent in the grid and the domino type determined by their labels equals $t$.

A 3-dimensional matching is a subset $M\subseteq \mathcal{T}$ such that no two distinct triples in $M$ share any element of $X$, or any element of $Y$, or any element of $Z$.

Suppose first that a valid Dominosa tiling is given. Each domino occupies exactly two adjacent cells $u,v$ whose labels determine a unique type $t\in D$, and each domino type is used exactly once. Associate to each placed domino the triple $(u,v,t)$. No cell occurs in two different dominoes, so no element of $X$ or $Y$ repeats in two triples. No domino type repeats, so no element of $Z$ repeats. Hence the resulting set of triples is a 3-dimensional matching in $\mathcal{T}$.

Conversely, suppose $M$ is a 3-dimensional matching in $\mathcal{T}$. Each $x\in X$ appears in exactly one triple of $M$, and each $y\in Y$ appears in exactly one triple of $M$. For each cell $u\in C$, there is exactly one triple $(u,v,t)$ or $(v,u,t)$ in $M$, so each cell is incident to exactly one selected adjacency. Since $Y$ is also covered exactly once, the selected triples pair cells into disjoint unordered pairs ${u,v}$, each corresponding to adjacent grid cells. Each such pair carries label multiset ${\lambda(u),\lambda(v)}$ equal to the associated $t\in Z$, and every $t\in Z$ appears exactly once, so each domino type is used exactly once. These pairs therefore form a valid Dominosa placement.

The constructions are inverse under projection from triples to domino placements and from placements to triples, so Dominosa reconstruction is an instance of 3-dimensional matching.

This completes the proof. ∎