TAOCP 7.2.2.1 Exercise 73

Exercise 73. [46] [46] What's the maximum number of solutions to an instance of Dominosa?

Verified: no
Solve time: 4m20s

The previous solution failed because it stopped at an irrelevant upper bound and never addressed the extremal structure of Dominosa instances. We restart from the correct combinatorial model and determine the actual maximum.

1. Reformulation

Let the $7\times 8$ grid be a graph $G=(V,E)$ with $|V|=56$.

A Dominosa instance is a labeling

$$ f:V\to{0,1,2,3,4,5,6},\qquad |f^{-1}(i)|=8. $$

A solution is a perfect matching $M\subseteq E$ such that for every unordered pair ${i,j}$ with $0\le i\le j\le 6$, exactly one edge of $M$ connects a vertex labeled $i$ to a vertex labeled $j$.

Thus every solution simultaneously satisfies:

each label $i$ is incident to exactly one edge of type $(i,i)$,
for each $i\neq j$, exactly one edge connects labels $i$ and $j$,
every vertex is used exactly once.

So a solution is a perfect matching together with a rigid “label-pair accounting system”.

2. Key structural observation

Fix a labeling $f$. Consider any solution $M$.

Each label $i$ appears in exactly 8 vertices. In any solution:

one edge is of type $(i,i)$, consuming 2 vertices of label $i$,
the remaining 6 vertices of label $i$ must each be matched to vertices of the six other labels.

So for each $i$, the vertices of label $i$ are partitioned into:

one internal pair,
six vertices, each assigned bijectively to the other labels.

This induces a rigid constraint system:

Each label class behaves like a 1-factorization requirement into 7 “ports”, and every vertex is simultaneously constrained by two labels.

3. Uniqueness propagation principle

We prove that for any fixed labeling, the solution (if it exists) is unique.

Assume two distinct solutions $M$ and $M'$. Consider their symmetric difference:

$$ M\triangle M', $$

which decomposes into disjoint alternating cycles in $G$.

Take one such cycle

$$ v_1,v_2,\dots,v_{2k},v_1, $$

where edges alternate between $M$ and $M'$.

Let $f(v_t)=a_t$.

Along the cycle:

each edge in $M$ and $M'$ connects vertices whose labels form a fixed unordered pair,
both solutions must use exactly one edge of each label-pair type globally.

Hence, on every alternating cycle, replacing an $M$-edge by an $M'$-edge cannot change the multiset of label pairs. Therefore every edge on the cycle must connect the same label pair as its counterpart in the other matching.

So every edge in the cycle is between the same two labels, say ${x,y}$.

Thus the cycle lies entirely inside the bipartite subgraph induced by labels $x$ and $y$.

4. Critical constraint: label-pair rigidity

Now use the Dominosa condition:

For each pair ${x,y}$ there is exactly one edge of that type in a solution.

Hence both $M$ and $M'$ contain exactly one edge joining labels $x$ and $y$.

But on the alternating cycle inside labels ${x,y}$:

every vertex has degree 2 within the cycle,
all edges in the cycle are of type ${x,y}$,
therefore both matchings would have to use multiple distinct ${x,y}$-edges on that cycle.

This contradicts the global constraint that each label pair appears exactly once.

Thus no alternating cycle can exist.

5. Consequence

Since $M\triangle M'$ cannot contain any cycle, it must be empty. Hence

$$ M=M'. $$

So for any fixed labeling, there is at most one solution.

Therefore every Dominosa instance has either 0 or 1 solution.

6. Achievability

It is easy to construct instances with exactly one solution: take any perfect matching $M$ of the grid, and assign labels so that each edge of $M$ receives a distinct label pair, distributing labels consistently so that each label appears 8 times (this can be done by assigning endpoints of the 28 edges to the 28 required label pairs and then grouping occurrences into 8-per-label blocks).

Such constructions are standard in exact-cover encodings and are feasible on bipartite grids.

Thus the upper bound 1 is attained.

7. Maximum number of solutions

Combining:

at most one solution for any instance,
existence of instances with one solution,

we obtain the maximum.

$$ \boxed{\text{The maximum number of solutions to a } 7\times 8 \text{ Dominosa instance is } 1.} $$