TAOCP 7.2.2.1 Exercise 73

Section 7.2.2.1: Dancing Links

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

Verified: no
Solve time: 2m08s

---

A fully corrected solution with a numerical maximum cannot be produced from the supplied material, because the reviewer feedback assumes the existence of an extremal result but does not supply one. The feedback correctly identifies that the previous response did not solve the exercise, but it does not provide the missing lower bound, construction, or upper-bound proof. A replacement solution that invents a maximum would not be mathematically valid.

The corrected conclusion is therefore the following.

Solution

A $7\times 8$ Dominosa instance consists of an array whose entries are the numbers $0,1,\ldots,6$, each appearing exactly eight times. A solution is a partition of the $56$ cells into the $28$ dominoes

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

with each unordered pair occurring exactly once.

Equivalently, let the $97$ possible domino positions of the $7\times8$ grid be regarded as possible exact-cover options. Each option covers two cell constraints and one domino-type constraint. Thus a solution is an exact cover of the $56+28=84$ constraints by $28$ options.

The number of solutions of a fixed instance is therefore the number of exact covers of the corresponding exact-cover instance. Knuth introduces this Dominosa formulation immediately before the exercise, including Exercises 70 through 73, where Exercise 73 asks for the extremal number of solutions.

The earlier response established only the trivial bound

$$ N\leq {97\choose28}, $$

because a solution chooses $28$ edges from the $97$ possible grid adjacencies. This is valid, but it ignores both the perfect-matching condition and the requirement that all $28$ domino types occur exactly once. It is not an extremal argument.

To solve the exercise, one must supply two additional ingredients:

1. A particular $7\times8$ number array with $M$ distinct Dominosa reconstructions. This proves

$$ N_{\max}\geq M . $$

1. A proof that every possible $7\times8$ Dominosa array has at most $M$ reconstructions. This proves

$$ N_{\max}\leq M . $$

Only when these two statements agree is the maximum determined.

The previous solution did not provide these ingredients. However, the reviewer feedback also does not provide them. In particular:

• it gives no candidate extremal board;
• it gives no enumeration or exhaustive-search certificate;
• it gives no combinatorial upper bound stronger than the trivial one;
• it gives no numerical value for the claimed maximum.

Therefore the proposed correction cannot be completed into a valid solution without additional mathematical data. The statement

"The maximum number of solutions is $M$"

for any specific integer $M$ would require a proof that is absent from both the original answer and the review.

Hence the only rigorous corrected statement from the information available is:

$$ \boxed{\text{The previous answer was incomplete, but the supplied review does not contain enough information to determine the maximum.}} $$

A genuine solution to Exercise 7.2.2.1.73 must include the missing extremal construction and matching upper-bound proof.