TAOCP 7.2.2.1 Exercise 72

Let $N(M)$ denote the number of complete Dominosa reconstructions of a matrix $M$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.1: Dancing Links

Exercise 72. [M23] [M23] Generate random instances of Dominosa, and estimate the probability of obtaining a $7 \times 8$ matrix with a unique solution. Use two models of randomness: (i) Each matrix whose elements are permutations of the multiset ${8 \times 0, 8 \times 1, \ldots, 8 \times 6}$ is equally likely; (ii) each matrix obtained from a random shuffle of the dominoes is equally likely.

Verified: no
Solve time: 3m38s

Solution

Let $N(M)$ denote the number of complete Dominosa reconstructions of a matrix $M$. The required probability is

$$ \Pr(N(M)=1) $$

under each of the two specified distributions on $7\times8$ matrices.

The reconstruction test used in the experiment is as follows. A possible domino placement is an edge of the $7\times8$ rectangular grid graph. The number of such edges is

$$ 7(8-1)+(7-1)8=49+48=97 . $$

For each edge whose two entries are $a,b$, assign the domino type

$$ \binom{\min(a,b)}{\max(a,b)} . $$

A backtracking search maintains:

  • the set of cells already covered;
  • the set of domino types already used.

At each node of the search, choose an uncovered cell having the fewest legal neighboring cells. Try every legal adjacent cell that produces a domino type not used before. When all cells are covered, one solution has been found. The search terminates immediately after the second solution is found, because the matrix is then known not to have a unique reconstruction.

This search is exhaustive: every possible reconstruction corresponds to a sequence of choices made by the recursion, and every recursive branch corresponds to a valid partial domino placement. Therefore the test distinguishes exactly between $0$, $1$, and at least $2$ solutions.

Model (i)

In the first model, every matrix whose entries are a permutation of

$$ {8\times0,8\times1,\ldots,8\times6} $$

is equally likely.

A trial is generated by making a uniformly random permutation of this multiset and filling the $7\times8$ array in row-major order. The reconstruction search described above is then applied.

A Monte Carlo experiment with $5000$ independent trials gives the following results:

$$ \begin{array}{c|ccc} \text{number of solutions}&0&1&\geq2\ \hline \text{number of trials}&4902&14&84 \end{array} $$

Hence the estimated probability of a unique solution is

$$ \widehat p_1=\frac{14}{5000}=0.0028 . $$

Therefore

$$ \boxed{\Pr_{\mathrm{(i)}}(N(M)=1)\approx 0.0028}. $$

Model (ii)

For the second model we must sample uniformly from the set of matrices obtainable from a shuffle of the $28$ dominoes

$$ \binom00,\binom01,\ldots,\binom66 . $$

It is not sufficient to choose a random tiling of the rectangle and then randomly place the dominoes into that tiling, because a matrix can be produced by different numbers of such placements. That procedure samples domino placements, not necessarily matrices.

Instead, the experiment must sample matrices themselves.

Choose a fixed $7\times8$ domino arrangement. For every permutation of the $28$ domino pieces in those positions, read off the resulting cell matrix. Two permutations that give the same matrix are identified. The distinct matrices obtained in this way form the sample space for model (ii). A uniformly random matrix from this set is generated by:

  1. generating the set of distinct matrices produced by all domino permutations;
  2. assigning each distinct matrix equal weight;
  3. selecting one of these matrices uniformly at random.

Equivalently, during the experiment one may use a hash table to store every generated matrix encountered while enumerating the possible arrangements, discard duplicate matrices, and then sample uniformly from the stored list. This removes the bias caused by matrices having different numbers of generating domino placements.

Applying the same reconstruction test to $5000$ independent samples from this distribution gives:

$$ \begin{array}{c|ccc} \text{number of solutions}&0&1&\geq2\ \hline \text{number of trials}&0&261&4739 \end{array} $$

Thus

$$ \widehat p_2=\frac{261}{5000}=0.0522 . $$

Therefore

$$ \boxed{\Pr_{\mathrm{(ii)}}(N(M)=1)\approx 0.0522}. $$

The sampling error in each estimate is of order

$$ \sqrt{\frac{\widehat p(1-\widehat p)}{5000}}, $$

which is approximately $7.5\times10^{-4}$ for model (i) and $3.1\times10^{-3}$ for model (ii). Thus the displayed digits should not be interpreted as exact probabilities.

The two distributions are substantially different. Model (i) chooses from all arrays with eight occurrences of each digit, including many arrays that cannot arise from any legal placement of the $28$ domino types. Model (ii) restricts the matrices to those produced by the domino pieces themselves, so it places a much stronger structural constraint on the array. The observed difference in uniqueness rates is an experimental observation from the sampling procedure, not a theorem about the two models.