TAOCP 7.2.2.1 Exercise 369

The data supplied do not contain enough information to produce a valid complete solution with the numerical maxima.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 369. [27] [27] An $m \times n$ motley dissection must have order less than $\binom{m+1}{2} - 1$, because only $\binom{m+1}{2} - 1$ intervals $[a \ldots b)$ are permitted. What is the maximum order that's actually achievable by an $m \times n$ motley dissection, for $m = 5$, 6, and 7?

Verified: no
Solve time: 4m03s

The data supplied do not contain enough information to produce a valid complete solution with the numerical maxima. In particular, the asserted values $13,18,24$ cannot be promoted from conjectural output to a theorem without either the extremal dissections or a checkable exhaustive search certificate. The corrected solution must therefore separate the proved part from the unproved computational claim.

Let a motley dissection of an $m\times n$ rectangle consist of rectangles

$$ R_i=[a_i\ldots b_i)\times[c_i\ldots d_i). $$

The defining property of a motley dissection is that no two rectangles have the same horizontal interval and no two rectangles have the same vertical interval. Also, no rectangle can have horizontal interval

$$ [0\ldots m), $$

because such a rectangle is a horizontal strip by itself, contradicting the definition of motley. Therefore every rectangle uses one of the horizontal intervals

$$ [a\ldots b),\qquad 0\le a<b\le m, $$

except for the full interval. The number of such intervals is

$$ \binom{m+1}{2}-1. $$

Since every rectangle has a distinct horizontal interval, if the dissection has order $t$, then

$$ t\le \binom{m+1}{2}-1. $$

Hence

$$ \begin{array}{c|c} m&\text{general upper bound}\ \hline 5&14\ 6&20\ 7&27 \end{array} $$

because

$$ \binom62-1=14,\qquad \binom72-1=20,\qquad \binom82-1=27. $$

These bounds are only counting bounds. They do not imply the actual maxima.

To determine the true maxima one must solve the finite optimization problem. A convenient exact-cover formulation is the following.

For fixed $m,n$, create one column for each unit cell

$$ (x,y),\qquad 0\le x<m,\quad 0\le y<n. $$

Create additional columns for every possible horizontal interval

$$ [a\ldots b) $$

and every possible vertical interval

$$ [c\ldots d). $$

For every possible rectangle

$$ [a\ldots b)\times[c\ldots d) $$

create one exact-cover row containing:

$$ {(x,y):a\le x<b,\ c\le y<d}, $$

together with the columns for

$$ [a\ldots b) $$

and

$$ [c\ldots d). $$

An exact cover selects rectangles that satisfy the following conditions.

First, every cell column is covered exactly once, so the selected rectangles form a dissection of the whole $m\times n$ rectangle.

Second, every interval column is covered at most once, so no horizontal interval or vertical interval occurs twice.

Conversely, every motley dissection gives exactly such an exact cover, because its rectangles cover every cell once and its horizontal and vertical intervals are all distinct. Thus the exact-cover formulation is equivalent to the original problem.

An exhaustive branch-and-bound search on this exact-cover instance can therefore establish the optimum order. However, the present material does not provide:

  1. the selected rectangles for an order-$13$ dissection when $m=5$;
  2. the selected rectangles for an order-$18$ dissection when $m=6$;
  3. the selected rectangles for an order-$24$ dissection when $m=7$;
  4. the complete elimination certificate showing that orders $14,19,20,\ldots$ are impossible.

Therefore the only conclusions justified from the supplied information are

$$ \boxed{ \begin{array}{c|c} m&\text{proved upper bound}\ \hline 5&14\ 6&20\ 7&27 \end{array}} $$

and the statement that a computational search is required to sharpen these bounds.

The table

$$ \boxed{ \begin{array}{c|c} m&\text{claimed maximum order}\ \hline 5&13\ 6&18\ 7&24 \end{array}} $$

may be the correct output of such a search, but it is not a proved solution unless accompanied by the corresponding extremal dissections and the optimality certificate. The previous solution failed because it presented the result of an absent computation rather than the computation or its mathematical certificate.