Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings?

Every integer rectangle area in the list (multiset) must be used exactly once (corresponds to exactly one rectangle).

For example, if we were given $$(2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1, 1, 20, 1)$$ then one possible integer rectangle tiling is:

enter image description here

which uses the given list to tile a $11\times 12$ rectangle.

So far, I've found What rectangles can a set of rectangles tile? on MO, and am trying to track down and adapt the references to my problem.

A similar but different problem is Filling rectangles with integer-sided squares.

  • $\begingroup$ Can each area in the list only be used once for a single piece? That is, no copies? Must each area be used, or can some be left out? $\endgroup$ – orlp Oct 11 '20 at 16:01
  • $\begingroup$ @orlp Every area must be used exactly once. (Notice multiple copies of area $1$ in the example list.) $\endgroup$ – Vepir Oct 11 '20 at 16:04
  • $\begingroup$ Please edit the question to incorporate the information into the question, rather than leaving a comment here. We want the question to be understandable without having to read the comments. Thank you! $\endgroup$ – D.W. Oct 11 '20 at 19:39

This answer assumes that you only allow the tiles to have integer sides.

There are always some trivial tilings, in which the rectangle being tiled has either a single row or a single column. Counting the number of these is simple combinatorics. Let us show that deciding whether there are any other tilings is NP-complete (under randomized reductions, or assuming some number-theoretic conjectures). It is clearly in NP. To show that it is NP-hard, we reduce from PARTITION. An instance of PARTITION is a multiset of positive integers, and the problem is to determine whether it can be partitioned into two multisets with equal sum.

We start by showing that PARTITION is NP-hard even if all parts are odd and the total sum is divisible by 4. Let us first ignore the latter requirement. Given an instance $S = \{x_1,\ldots,x_n\}$ of PARTITION, construct an instance of the new problem with $S' = \{2nx_1+1,\ldots,2nx_n+1\} \cup \{1^n\}$ (here $1^n$ mean $n$ many $1$s).

If the original instance can be partitioned into two equal parts, say $\{x_1,\ldots,x_m\}$ and $\{x_{m+1},\ldots,x_n\}$, then so can the new instance. Indeed, consider the multiset $\{2nx_1+1,\ldots,2nx_m+1\}$, together with $n-m$ many $1$s. This multiset sums to $2n(x_1 + \cdots + x_m) + m + (n-m) = 2n(x_1 + \cdots + x_m) + n$. Similarly, the remaining numbers sum to $2n(x_{m+1} + \cdots + x_n) + (n-m) + m = 2n(x_{m+1} + \cdots + x_n) = n$, which is identical.

Conversely, suppose that $S'$ can be partitioned into two equal parts, say one of them consisting of $2nx_1+1,\ldots,2nx_m+1$ together with $r$ many $1$s. It follows that $$ 2n(x_1 + \cdots + x_m) + m + r = 2n(x_{m+1} + \cdots + x_n) + (n-m) + (n-r), $$ and so $$ 2n(x_1 + \cdots + x_m - x_{m+1} - \cdots - x_n) = (n-2m) + (n-2r). $$ Since $1 \leq m \leq n-1$ and $0 \leq r \leq n$, the right-hand side is in the range $[-(2n-2),(2n-2)]$. Since the left-hand side is a multiple of $2n$, we conclude that the right-hand size is zero, and so $x_1 + \cdots + x_m = x_{m+1} + \cdots + x_n$.

Let us now attend to the sum of $S'$. If $S$ sums to $2R$ then $S'$ sums to $$ 2n \cdot 2R + 2n = 2n(2R+1). $$ Therefore if $n$ is even, then we are done. Otherwise, we can replace $n$ with $n+1$ throughout (equivalently, add a zero to $S$).

We now reduce the PARTITION variant to the tiling problem. Let $S$ be an instance of PARTITION in which all numbers are odd and the sum is $2T$, where $T$ is even. Let $p$ be a prime in $(2T,3T)$. Notice that $S \cup \{p-T,p-T\}$ can be partitioned into two equal halves iff $S$ can (this is since $2(p-T)$ is larger than half the total sum, which is $[2T+2(p-T)]/2 = p$). Moreover, since $p$ is odd and $T$ is even, $p-T$ is odd.

Let $q \in (2p,3p)$ be a prime, and consider the instance $S \cup \{p-T,p-T,pq\}$. If $S$ can be partitioned into two equal halves, then we can tile a rectangle of dimensions $p \times (q+2)$ by taking a rectangle of dimensions $p \times q$ and adding two more columns corresponding to the two equal halves of $S \cup \{p-T,p-T\}$.

Conversely, suppose that $S \cup \{p-T,p-T,pq\}$ can tile some rectangle. Since $p,q$ are prime, the rectangle of area $pq$ must have dimensions $1 \times pq$ or $p \times q$ (up to switching the axes). In the former case, since all remaining numbers add up to $2p < pq$, we end up with a trivial tiling. In the latter case, since $2p < q$, the remaining numbers are not enough to fill any rows, and so we conclude that the tiled rectangle must have exactly $p$ rows. Since the remaining numbers add up to $2p$, they must tile a $p \times 2$ rectangle (or two $p \times 1$ rectangles, which is a stronger requirement). The remaining numbers are all odd, and so must correspond to rectangles with a single column. This is only possible if they can be partitioned into two equal parts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.