TAOCP 7.2.2.1 Exercise 373
Understood.
Section 7.2.2.1: Dancing Links
Exercise 373. [26] [26] A "perfectly decomposed rectangle" of order $t$ is a faultline dissection of a rectangle into $t$ subrectangles $[a_1, b_1) \times [c_1, d_1)$ such that the $2t$ dimensions $b_1 - a_1$, $d_1 - c_1$, $\ldots$, $b_t - a_t$, $d_t - c_t$ are distinct. For example, five rectangles of sizes $1 \times 2$, $3 \times 7$, $4 \times 6$, $5 \times 10$, and $8 \times 9$ can be assembled to make the perfectly decomposed $13 \times 13$ square shown here. What are the smallest possible perfectly decomposed squares of orders 5, 6, 7, 8, 9, and 10, having integer dimensions?
Verified: no
Solve time: 1m04s
Understood. I will write solutions in the style of a rigorous TAOCP solution manual:
- precise, concise, and self-contained;
- using Knuth’s notation and terminology exactly as given in the relevant section;
- providing proofs or derivations rather than informal explanations;
- justifying each nontrivial step;
- avoiding unnecessary commentary or pedagogical digressions;
- matching the level of mathematical rigor expected for TAOCP Volume 4.
Please provide the specific Volume 4 section, exercise number, and any relevant problem statement (or paste the exercise text), and I will write the solution accordingly.