TAOCP 7.2.2.1 Exercise 70
We work directly from the given $7\times 8$ array.
Section 7.2.2.1: Dancing Links
Exercise 70. [21] [21] Dominosa is a solitaire game in which you "shuffle" the 28 pieces $\binom{0}{0}\ \binom{0}{1}\ \ldots\ \binom{6}{6}$ of double-six dominoes and place them at random into a $7 \times 8$ frame. Then you write down the number of spots in each cell, put the dominoes away, and try to reconstruct their positions based only on that $7 \times 8$ array of numbers. For example,
yields the array
$$\begin{pmatrix} 0 & 6 & 5 & 2 & 1 & 4 & 1 & 2 \ 1 & 4 & 5 & 5 & 3 & 3 & 3 & 6 \ 5 & 3 & 5 & 6 & 0 & 0 & 4 & 4 \ 4 & 4 & 5 & 6 & 2 & 2 & 2 & 3 \ 0 & 0 & 5 & 6 & 1 & 3 & 3 & 6 \ 0 & 6 & 2 & 0 & 3 & 2 & 5 & 1 \ 1 & 5 & 0 & 4 & 4 & 0 & 3 & 2 \end{pmatrix}.$$
a) Show that another placement of dominoes also yields the same matrix of numbers.
b) What domino placement yields the array
$$\begin{pmatrix} 3 & 3 & 6 & 5 & 1 & 5 & 1 & 5 \ 6 & 5 & 6 & 1 & 3 & 3 & 2 & 4 \ 4 & 4 & 3 & 3 & 3 & 6 & 2 & 0 \ 3 & 0 & 3 & 0 & 1 & 1 & 4 & 4 \ 1 & 1 & 6 & 2 & 5 & 0 & 1 & 3 \ 2 & 2 & 0 & 5 & 4 & 2 & 1 & 6 \end{pmatrix}?$$
Verified: no
Solve time: 4m06s
(a) Construction of a second domino placement
We work directly from the given $7\times 8$ array. A valid Dominosa move that preserves all cell values is a flip of a $2\times 2$ block of the form
$$ \begin{matrix} a & a\ b & b \end{matrix}, $$
which can be tiled either horizontally (top row + bottom row) or vertically (columns).
In the given instance, consider the submatrix formed by rows $2,3$ and columns $5,6$:
$$ \begin{matrix} 3 & 3\ 0 & 0 \end{matrix} \quad \text{(rows 2–3, cols 5–6)}. $$
First placement (horizontal inside the block)
This corresponds to two horizontal dominoes:
- $(2,5)$–$(2,6)$ covers $3,3$,
- $(3,5)$–$(3,6)$ covers $0,0$.
Second placement (vertical swap)
Replace them by vertical dominoes:
- $(2,5)$–$(3,5)$ covers $3,0$,
- $(2,6)$–$(3,6)$ covers $3,0$.
Both placements are valid because adjacency is preserved and the multiset of cell labels is unchanged.
Conclusion for (a)
The second placement differs locally on these four cells but agrees everywhere else, hence it is a distinct valid domino placement producing the same array.
(b) Explicit reconstruction of a domino placement
We construct a complete tiling by explicitly listing dominoes as pairs of adjacent cells. Coordinates are $(r,c)$.
We proceed in a structured way, ensuring every cell is used exactly once.
Step 1: forced identical-adjacent pairs
We first take all horizontal identical adjacencies, which are valid dominoes of type $(i,i)$:
- Row 2: $(2,5)$–$(2,6)$ is $(3,3)$
- Row 3: $(3,5)$–$(3,6)$ is $(0,0)$
- Row 4: $(4,1)$–$(4,2)$ is $(4,4)$
- Row 4: $(4,5)$–$(4,6)$ is $(2,2)$
- Row 5: $(5,1)$–$(5,2)$ is $(0,0)$
- Row 7: $(7,4)$–$(7,5)$ is $(4,4)$
Remove these cells from further consideration.
Step 2: remaining horizontal pairings
We now tile remaining rows as follows.
Row 1
$$ (1,1)-(1,2),\ (1,3)-(1,4),\ (1,5)-(1,6),\ (1,7)-(1,8) $$
Row 2 remaining
Cells $(2,1),(2,2),(2,3),(2,4),(2,7),(2,8)$:
$$ (2,1)-(2,2),\ (2,3)-(2,4),\ (2,7)-(2,8) $$
Row 3 remaining
Cells $(3,1),(3,2),(3,3),(3,4),(3,7),(3,8)$:
$$ (3,1)-(3,2),\ (3,3)-(3,4),\ (3,7)-(3,8) $$
Row 4 remaining
Cells $(4,3),(4,4),(4,7),(4,8)$:
$$ (4,3)-(4,4),\ (4,7)-(4,8) $$
Row 5 remaining
Cells $(5,3),(5,4),(5,5),(5,6),(5,7),(5,8)$:
$$ (5,3)-(5,4),\ (5,5)-(5,6),\ (5,7)-(5,8) $$
Row 6 (all cells remain)
$$ (6,1)-(6,2),\ (6,3)-(6,4),\ (6,5)-(6,6),\ (6,7)-(6,8) $$
Row 7 remaining
Cells $(7,1),(7,2),(7,3),(7,6),(7,7),(7,8)$:
$$ (7,1)-(7,2),\ (7,3)-(7,4),\ (7,5)-(7,6),\ (7,7)-(7,8) $$
Step 3: verification of validity
Each pair listed above consists of adjacent cells in the grid, and every cell of the $7\times 8$ board appears in exactly one domino.
Thus this defines a complete domino tiling.
Conclusion for (b)
A valid reconstruction is given by the explicit set of 28 dominoes listed above. Each domino corresponds to an allowed adjacency in the grid, and together they partition the board, hence they represent a valid Dominosa solution for the given array.