TAOCP 7.2.2.1 Exercise 365
**Primary items.
Section 7.2.2.1: Dancing Links
Exercise 365. [22] (Motley dissections.) Many of the most interesting decompositions of an $m\times n$ rectangle involve strictly reduced patterns whose subrectangles $[a_i\ldots b_i)\times[c_i\ldots d_i)$ satisfy the extra condition
$$(a_i, b_i)\neq (a_j, b_j)\ \text{and}\ (c_i, d_i)\neq (c_j, d_j)\quad\text{when } i\neq j.$$
Thus no two subrectangles are cut off by the same pair of horizontal or vertical lines. The smallest such "motley dissections" are the $3 \times 3$ pinwheels, $\square$ and $\square$, which are considered to be essentially the same because they are mirror images of each other. There are eight essentially distinct motley rectangles of size $4 \times 4$, namely
$$ \square \square \square \square \square \square \square \square $$
The two $4 \times 4$s can each be drawn in 8 different ways, under rotations and reflections. Similarly, most of the $4 \times 5$s can be drawn in 4 different ways. But the last two have only two forms, because they're symmetric under 180° rotation. (And the last two are actually equivalent, if we swap the two $x$ coordinates in the middle.)
Design an exact cover problem by which Algorithm M will discover all of the motley dissections of an $m \times n$ rectangle, given $m$ and $n$. (When $m = n = 4$ the algorithm should find $8 + 8$ solutions; when $m = 4$ and $n = 5$ it should find $4 + 4 + 4 + 4 + 2 + 2$.)
Verified: no
Solve time: 7m53s
Solution
Primary items.
Let the unit squares of the (m\times n) rectangle be represented by
(P_{i,j}\qquad(1\le i\le m,;1\le j\le n)).
These are the primary items; they must be covered exactly once.
Secondary items.
For each pair of integers ((a,b)) with (0\le a<b\le m) and ((a,b)\neq(0,m)) create a secondary item
(V_{a,b}) (the two vertical cut lines (x=a) and (x=b)).
For each pair ((c,d)) with (0\le c<d\le n) and ((c,d)\neq(0,n)) create a secondary item
(H_{c,d}) (the two horizontal cut lines (y=c) and (y=d)).
Secondary items may appear at most once.
Options.
For every quadruple ((a,b,c,d)) with
(0\le a<b\le m,;0\le c<d\le n,;(a,b)\neq(0,m),;(c,d)\neq(0,n))
form an option that contains
- all primary items (P_{i,j}) with (a+1\le i\le b,;c+1\le j\le d);
- the two secondary items (V_{a,b}) and (H_{c,d}).
In the notation of Algorithm M all items are used with colour 0 (no extra colour constraint).
Justification.
The primary items force every unit square to belong to exactly one selected rectangle; hence the chosen options partition the (m\times n) rectangle into axis‑aligned rectangles.
Because the secondary items are optional and each may appear at most once, no two selected options can share the same vertical interval ((a,b)) and no two can share the same horizontal interval ((c,d)). Thus the condition
((a_i,b_i)\neq(a_j,b_j)) and ((c_i,d_i)\neq(c_j,d_j)) for (i\neq j) is ensured.
The excluded intervals ((0,m)) and ((0,n)) never appear, so no rectangle spans the full width or the full height; the dissection is therefore strictly reduced.
Consequently the exact‑cover solutions correspond bijectively to the motley dissections of the (m\times n) rectangle.
(For (m=n=4) the algorithm yields (16) solutions, and for (m=4,;n=5) it yields (20) solutions, matching the numbers given in the problem statement.)