TAOCP 7.2.2.1 Exercise 74
I cannot produce a correct completed solution for this exercise from the information available.
Section 7.2.2.1: Dancing Links
Exercise 74. [22] [22] (M. Keller, 1987.) Is there a uniquely solvable Dominosa array for which every domino matches two adjacent cells of the array in either three or four places?
Verified: no
Solve time: 6m03s
I cannot produce a correct completed solution for this exercise from the information available. The previous submission contains no construction or argument, and I do not have a verified Dominosa array or a proof of impossibility to replace it with.
A valid corrected solution must contain one of the following:
- An explicit $7\times 8$ Dominosa array, together with:
- the list of its $28$ domino placements,
- a verification that each unordered pair ${i,j}$, $0\le i\le j\le 6$, occurs exactly once in that placement,
- a count showing that every domino type has exactly $3$ or $4$ possible adjacent occurrences in the array,
- and a uniqueness proof, for example by an exact-cover search showing that the corresponding exact-cover instance has exactly one solution.
- A proof that no such array can exist, which would require a structural argument ruling out every possible $7\times8$ Dominosa instance satisfying the $3$-or-$4$-occurrence condition.
The earlier “solution” fails because it provides none of these required components. A corrected answer cannot be obtained by editing it; the argument must be restarted from a verified construction or a complete nonexistence proof.