TAOCP 7.2.2.1 Exercise 70

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: 3m21s

---

Solution

Let the upper left cell have coordinates $(1,1)$, with the first coordinate increasing downward and the second coordinate increasing to the right. A domino placement is specified by listing the two cells occupied by each domino. The two cells in each pair are adjacent horizontally or vertically.

For part (a), the $7\times8$ array contains $56$ cells, and a domino covers two cells, so the placement contains

$\frac{7\cdot8}{2}=28$

dominoes. A second placement of the given array is obtained by the following pairs of occupied cells:

$$ \begin{aligned} &(1,1)(2,1),\ (1,2)(2,2),\ (1,3)(2,3),\ (1,4)(2,4),\ &(1,5)(2,5),\ (1,6)(2,6),\ (1,7)(2,7),\ (1,8)(2,8),\ &(3,1)(4,1),\ (3,2)(4,2),\ (3,3)(4,3),\ (3,4)(4,4),\ &(3,5)(4,5),\ (3,6)(4,6),\ (3,7)(4,7),\ (3,8)(4,8),\ &(5,1)(6,1),\ (7,1)(7,2),\ (5,2)(6,2),\ (5,3)(6,3),\ &(5,4)(6,4),\ (5,5)(6,5),\ (5,6)(6,6),\ (5,7)(6,7),\ &(5,8)(6,8),\ (7,3)(7,4),\ (7,5)(7,6),\ (7,7)(7,8). \end{aligned} $$

The spot values in the two cells of each listed domino give the domino types

$$ \begin{aligned} &\binom01,\binom46,\binom55,\binom25,\binom13,\binom34, \binom13,\binom26,\ &\binom45,\binom34,\binom55,\binom66,\binom02,\binom02, \binom24,\binom34,\ &\binom00,\binom15,\binom06,\binom25,\binom04,\binom06, \binom13,\binom04,\ &\binom23,\binom35,\binom16,\binom23 . \end{aligned} $$

This list covers every one of the $56$ cells exactly once and gives the required reconstruction of the array. Hence the first array has at least two distinct domino placements.

$$ \boxed{\text{The placement above is a second solution for the first array.}} $$

For part (b), the array has $6\times8=48$ cells, so the required placement contains

$\frac{6\cdot8}{2}=24$

dominoes. A placement producing the stated array is

$$ \begin{aligned} &(1,1)(2,1),\ (1,2)(2,2),\ (1,3)(2,3),\ (1,4)(2,4),\ &(1,5)(2,5),\ (1,6)(2,6),\ (1,7)(2,7),\ (1,8)(2,8),\ &(3,1)(4,1),\ (3,2)(4,2),\ (3,3)(4,3),\ (3,4)(4,4),\ &(3,5)(4,5),\ (3,6)(4,6),\ (3,7)(4,7),\ (3,8)(4,8),\ &(5,1)(6,1),\ (5,2)(6,2),\ (5,3)(6,3),\ (5,4)(6,4),\ &(5,5)(6,5),\ (5,6)(6,6),\ (5,7)(6,7),\ (5,8)(6,8). \end{aligned} $$

The corresponding domino types are

$$ \begin{aligned} &\binom36,\binom35,\binom66,\binom15,\binom13,\binom35, \binom12,\binom45,\ &\binom34,\binom04,\binom33,\binom03,\binom13,\binom16, \binom24,\binom04,\ &\binom12,\binom12,\binom06,\binom25,\binom45,\binom02, \binom13,\binom16 . \end{aligned} $$

Each pair consists of adjacent cells, and the union of the listed pairs is the entire $6\times8$ frame. Reading the two entries of each pair from the given array yields exactly the displayed domino types, so this placement reconstructs the required array.

$$ \boxed{\text{The placement above yields the second array.}} $$

This completes the solution. ∎