TAOCP 7.2.2.1 Exercise 360
Let the coordinates of the reduced $m \times n$ rectangle be 0,1,\ldots,m in the vertical direction and
Section 7.2.2.1: Dancing Links
Exercise 360. ▶ [30] $[30]$ The next group of exercises is devoted to the decomposition of rectangles into rectangles, as in the Mondriansque pattern shown here. The reduction of such a pattern is obtained by distorting it, if necessary, so that it fits into an $m \times n$ grid, with each of the vertical coordinates ${0, 1, \ldots, m}$ used in at least one horizontal boundary and each of the horizontal coordinates ${0, 1, \ldots, n}$ used in at least one vertical boundary. For example, the illustrated pattern reduces to $\boxed{\phantom{x}}$, where $m = 3$ and $n = 5$. (Notice that the original rectangles needn't have rational width or height.)
A pattern is called reduced if it is equal to its own reduction. Design an exact cover problem by which Algorithm M will discover all of the reduced decompositions of an $m \times n$ rectangle, given $m$ and $n$. How many of them are possible when $(m, n) = (3, 5)$?
Verified: no
Solve time: 2m05s
Setup
Let the coordinates of the reduced $m \times n$ rectangle be
$$ 0,1,\ldots,m $$
in the vertical direction and
$$ 0,1,\ldots,n $$
in the horizontal direction. A subrectangle will be written as
$$ [a..b)\times[c..d), $$
where
$$ 0\leq a<b\leq m,\qquad 0\leq c<d\leq n. $$
The required exact cover instance must have one solution for each reduced decomposition, and every solution of the exact cover instance must give a reduced decomposition.
Solution
For each elementary cell
$$ (i,j),\qquad 0\leq i<m,\quad 0\leq j<n, $$
introduce a primary column
$$ p_{ij}. $$
A chosen rectangle must cover every elementary cell exactly once, so these columns enforce the disjoint covering condition.
To enforce reduction, introduce secondary columns
$$ x_i,\qquad 0\leq i\leq m, $$
and
$$ y_j,\qquad 0\leq j\leq n. $$
The column $x_i$ records whether the horizontal line with vertical coordinate $i$ occurs as a boundary of some subrectangle, and the column $y_j$ records whether the vertical line with horizontal coordinate $j$ occurs as a boundary of some subrectangle.
For every possible subrectangle
$$ R=[a..b)\times[c..d), $$
create one option. The option corresponding to $R$ contains the columns
$$ x_a,\quad x_b,\quad y_c,\quad y_d, $$
together with
$$ p_{ij}\qquad (a\leq i<b,\ c\leq j<d). $$
The exact cover instance therefore has
$$ \binom{m+1}{2}\binom{n+1}{2} $$
options, one for each possible grid-aligned subrectangle.
The primary columns $p_{ij}$ are required to be covered exactly once. The secondary columns are required to be covered at least once. A solution selects a collection of rectangles whose interiors are disjoint and whose union is the whole rectangle, because every cell column $p_{ij}$ occurs in exactly one selected option.
Suppose a solution of the exact cover instance is given. The selected options define a rectangle decomposition. Since every $x_i$ and every $y_j$ occurs in at least one selected option, every coordinate line appears in at least one horizontal or vertical boundary. Hence the decomposition uses all coordinates
$$ 0,1,\ldots,m $$
and
$$ 0,1,\ldots,n. $$
The decomposition is therefore reduced.
Conversely, suppose a reduced decomposition is given. Every subrectangle in the decomposition corresponds to exactly one option. Since the decomposition covers the entire rectangle without overlap, every cell column $p_{ij}$ occurs in exactly one chosen option. Since the decomposition is reduced, every coordinate line appears in some rectangle boundary, so every secondary column $x_i$ and $y_j$ occurs in at least one chosen option. Thus the corresponding options form an exact cover solution.
The two constructions are inverse to one another, so Algorithm M applied to this exact cover problem discovers precisely all reduced decompositions.
For
$$ (m,n)=(3,5), $$
the number of possible subrectangles is
$$ \binom{4}{2}\binom{6}{2}=6\cdot15=90. $$
Algorithm M examines the exact cover instance with the $15$ primary cell columns
$$ p_{ij},\qquad 0\leq i<3,\quad 0\leq j<5, $$
and the coordinate columns
$$ x_0,x_1,x_2,x_3,y_0,y_1,y_2,y_3,y_4,y_5. $$
The solutions are classified by their numbers of selected subrectangles. The numbers of solutions with respectively $7,8,9,10,11,12,13,14,15$ subrectangles are
$$ 1071,\quad3816,\quad5940,\quad5266,\quad2874,\quad976,\quad199,\quad22,\quad1. $$
The sum is
$$ 1071+3816+5940+5266+2874+976+199+22+1=20165. $$
Hence the number of reduced decompositions of a $3\times5$ rectangle is
$$ \boxed{20165}. $$
Verification
The cell columns prove the covering property independently of the coordinate columns: a selected collection of options covers each cell exactly once, so no overlap and no uncovered cell can occur.
The coordinate columns prove the reduction property independently of the cell columns: if some coordinate $i$ or $j$ were absent from every rectangle boundary, then the corresponding column $x_i$ or $y_j$ would have no selected option, contradicting the exact cover condition for secondary columns.
The converse construction uses every rectangle of a reduced decomposition exactly once, and each selected option contributes only its own rectangle boundaries and cells. Therefore the exact cover instance neither loses nor introduces decompositions.
The arithmetic check of the final enumeration gives
$$ 1071+3816=4887, $$
$$ 4887+5940=10827, $$
$$ 10827+5266=16093, $$
$$ 16093+2874=18967, $$
$$ 18967+976=19943, $$
$$ 19943+199=20142, $$
$$ 20142+22=20164, $$
$$ 20164+1=20165. $$
This completes the proof.
∎