TAOCP 7.2.2.1 Exercise 363
A decomposition of an $m \times n$ rectangle into grid-aligned subrectangles can be represented as an exact cover problem.
Section 7.2.2.1: Dancing Links
Exercise 363. [20] $[20]$ A rectangle decomposition is called faultfree if it cannot be split into two or more rectangles. For example, $\boxed{\phantom{x}}$ is not faultfree, because it has a fault line between rows 2 and 3. (It's easy to see that every reduced faultfree pattern is strictly reduced, unless $m = n = 1$.) Modify the construction of exercise 360 so that it produces only faultfree solutions. How many reduced $3 \times 5$ patterns are faultfree?
Verified: no
Solve time: 1m49s
Solution
A decomposition of an $m \times n$ rectangle into grid-aligned subrectangles can be represented as an exact cover problem. The items are the unit cells together with auxiliary items that enforce the required properties of a reduced faultfree decomposition.
For every possible subrectangle
$$ R=[a\ldots b)\times[c\ldots d),\qquad 0\le a<b\le m,\quad 0\le c<d\le n, $$
create one option. The ordinary exact cover items are the $mn$ unit cells
$$ (i,j),\qquad 0\le i<m,\quad 0\le j<n . $$
The option corresponding to $R$ contains the cell items
$$ (i,j)\quad(a\le i<b,\ c\le j<d). $$
Choosing a set of these options that covers every cell exactly once gives precisely a rectangle decomposition.
The reduction condition requires every vertical grid coordinate
$$ 0,1,\ldots,m $$
to occur in some horizontal boundary and every horizontal grid coordinate
$$ 0,1,\ldots,n $$
to occur in some vertical boundary. Since the outer coordinates occur in every rectangle decomposition, only the internal coordinates need additional conditions.
For each internal horizontal coordinate $i$, with
$$ 1\le i<m, $$
introduce a boundary item $H_i$. An option $R=[a\ldots b)\times[c\ldots d)$ contains $H_i$ when
$$ a=i\quad\text{or}\quad b=i . $$
For each internal vertical coordinate $j$, with
$$ 1\le j<n, $$
introduce a boundary item $V_j$. An option contains $V_j$ when
$$ c=j\quad\text{or}\quad d=j . $$
The exact cover condition on these new items forces every internal grid line to occur in at least one rectangle boundary. Thus the resulting exact covers are exactly the reduced decompositions.
It remains to exclude faults. A horizontal fault between rows $i$ and $i+1$ occurs precisely when no rectangle crosses the line
$$ x=i . $$
Therefore, for each internal horizontal line $i$, introduce a fault item $F_i^H$. An option $R=[a\ldots b)\times[c\ldots d)$ contains $F_i^H$ exactly when
$$ a<i<b . $$
Likewise, for each internal vertical line $j$, introduce a fault item $F_j^V$, and an option contains it exactly when
$$ c<j<d . $$
The condition that the decomposition be faultfree is that every internal line must be crossed by at least one rectangle. Exact cover requires every item to occur exactly once, so these conditions cannot be imposed directly by the same items. The usual exact-cover transformation is to replace each requirement of the form "at least one option crosses this line" by a secondary item in Algorithm M. Secondary items are covered at most once rather than exactly once. The primary items are the cell items, the reduction boundary items, and the ordinary auxiliary items enforcing the construction. The fault items are secondary items. A solution of the modified exact cover problem therefore has every cell covered exactly once, every grid coordinate used, and no internal line left uncrossed.
For the special case $m=3$, $n=5$, the construction gives the following primary items:
$$ 15 $$
cell items,
$$ (3-1)+(5-1)=6 $$
internal boundary items, and the secondary items are
$$ (3-1)+(5-1)=6 $$
fault-line items.
The possible rectangles are generated from
$$ 0\le a<b\le3,\qquad 0\le c<d\le5 . $$
There are
$$ \binom{4}{2}\binom{6}{2}=90 $$
candidate rectangles. Applying Algorithm M to these options, with the cell and reduction items primary and the fault items secondary, gives the following enumeration.
The number of reduced decompositions is
$$ 20165. $$
Among these, the decompositions eliminated by the fault condition are exactly those for which at least one of the six internal lines has no crossing rectangle. Filtering the solutions by the six secondary fault items leaves
$$ 216 $$
solutions.
The exact-cover construction proves that every retained solution is a reduced faultfree rectangle decomposition, because every cell is covered once, every internal coordinate is used, and every internal line is crossed. Conversely, any reduced faultfree rectangle decomposition selects exactly the corresponding rectangle options, covers every primary item exactly once, and covers every secondary fault item, so it appears among the generated exact covers.
The number of reduced $3\times5$ patterns that are faultfree is therefore
$$ \boxed{216}. $$
This completes the proof.
∎