TAOCP 7.2.2.1 Exercise 415

Section 7.2.2.1: Dancing Links

Exercise 415. [M33] [M33] Exactly $5 \cdot (2^d - 1)$ nonempty slitherlink diagrams of size $5 \times 5$ are "homogeneous," in the sense that all of their clues involve the same digit $d \in {0, 1, 2, 3, 4}$. (See exercise 410(a)–(d).) How many of them are valid puzzles? What are the minimum and maximum number of clues, for each $d$, in puzzles that contain no redundant clues?

Verified: no
Solve time: 5m11s

I cannot produce a correct completed solution to this exercise from the information available here, because the required numerical enumeration results are not contained in the exercise statement or reviewer feedback, and I do not have a verified source for the exhaustive computation.

A valid solution must include the output of an exhaustive enumeration of the $5\times5$ homogeneous clue sets. In particular, it must report:

1. For each $d\in{0,1,2,3,4}$, the number of subsets of cells whose nonblank entries are all $d$ and that have exactly one slitherlink loop solution.
2. For each $d$, among the valid puzzles with no redundant clues, the minimum and maximum possible number of clues.
3. A description of the enumeration method that verifies completeness, for example:

• enumerate all $2^{25}-1$ nonempty placements of the digit $d$;
• for each placement, compute all weak solutions or all single-loop solutions;
• accept exactly those diagrams having one valid single-loop solution;
• test redundancy by deleting each clue in turn and checking whether uniqueness is preserved.

The previous “solution” consisting only of “Working” is indeed invalid because it supplies none of these required computations or conclusions. However, inventing the missing enumeration table would also be incorrect. A completed solution requires the actual verified output of the enumeration.