This is the story behind sequence A355477 from the Online Encyclopedia of Integer Sequences.

Let’s say you have an unlimited supply of “zig-zag” Tetris pieces:

How many can you pack into an n x n square?

For example, if you’re trying to fill a 4×4 square, then you can fit three such pieces:

but, try as you might, you’ll never get a fourth piece in there (without any of the pieces overlapping or poking out the sides of the square). What about a 5×5 square, a 6×6 square, etc.?

Our goal is to answer this question (reasonably) efficiently to find, for example, that this packing of a 16×16 square with 60 tiles is optimal:

It turns out that we know such optimal packings for squares up to 21 x 21, as well as a handful of larger values, but the problem is not completely solved yet. The rest of this post explains what’s known and how we know it.

Set Packing

This tiling problem is a nice example of the “Maximum Set Packing” problem, which is a classic optimization problem that has many applications. Specifically, if we label each square with a letter:

then any placement of a tile corresponds to a 4-element set of squares. For example, the three tiles in Figure 1 correspond to the sets:

$$\begin{array}\\ S_1 &=& \{B, C, E, F\} \\ S_2 &=& \{D, G, H, K\} \\ S_3 &=& \{I, J, N, O\} \end{array}.$$

And, in addition to these three sets, there are 21 other sets corresponding to other placements of zig-zag tiles (e.g., for a tile in the bottom-right corner, etc.) that we didn’t end up using in Figure 1, for a total of 24 possible placements of tiles within a 4×4 square.

The goal of the set packing problem is to find a collection of non-overlapping sets (from this family of 24 sets) that is as large as possible, which is equivalent to trying to squeeze as many non-overlapping tiles as possible into the square.

Unfortunately, the maximum set packing problem is NP-complete, so we’re not going to find an efficient algorithm that works in all cases, but there is still hope: Integer Programming.

Integer Programming

Integer programming is also a very hard computation problem, but there are excellent “mixed integer programming solvers” that work very well in practice on set-packing/tiling problems like these, so we’re going to take advantage of that as we try to understand this tiling question.

Let’s return to the 4×4 tiling example we looked at above and see how it can be transformed into an “integer programming” problem. First, it will be convenient to express this problem as matrix with 16 columns (each corresponding to one of the cells in the 4×4 square) and with rows corresponding to each possible placement of a tile. For example, these four placements of tiles:

correspond to the first four rows of the matrix :

$$ X = \begin{matrix}A & B & C & D & E & F & G & H & I & J &K & L & M & N & O &P \\ \hline 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{matrix}$$

The complete matrix has rows corresponding to all the different possible placements/orientations of the zig-zag tile.

Now, the tiling problem is equivalent to finding as many rows of as possible that have at most one in each column. This is easily expressed as an integer programming problem as follows:

Define binary variables

$$ s_1, \ldots, s_n \in \{0, 1\}$$

where is the number of rows in the matrix , and then

$$ \textrm{maximize } s_1 + \cdots + s_n$$

$$ \textrm{subject to}$$

$$ \vec{s} \cdot X \leq 1 $$

In code (using the ‘mip’ package for python) this would look something like:

def maxSetPacking(X):
    # Find the largest subset of disjoint rows of X
    m = mip.Model(sense=mip.MAXIMIZE)
    S = m.add_var_tensor((X.shape[0],), 'X', var_type=mip.BINARY)
    m.objective = S.sum()
    m += (np.dot(S, X) <= 1)
    m.optimize()
    return np.array([s.x for s in S]).round().astype(bool)

The result of this optimization is a boolean vector indicating which of the rows of form an optimal set covering.

Hmmmm… that’s odd

Here’s one interesting pattern that emerges from the optimal packings shown above: whenever is odd, then the optimal packing contains exactly $$\left( \frac{n-1}{2}\right)^2$$ tiles. And, in fact, this is true for all odd . Here’s a simple proof, using the case as an example:

First off, we can simply arrange the tiles in an interlocking array to fit tiles into the grid:

And, in general, the same approach will allow $$\left( \frac{n-1}{2}\right)^2$$ tiles to fit within an square whenever is odd, so we have:

$$a(n) \geq \left( \frac{n-1}{2}\right)^2$$

Now we have to show that no more than tiles can fit into an grid. To prove this, take the grid and place an “X” in the cells that are in both an even-numbered row and an even-numbered column:

Now observe that no matter where a tile is placed it will cover one of the “X”s, for example:

Since there are only “X”s, no more than tiles can be placed in the grid. (Otherwise, at least two of them would have to share an “X”, which would mean they overlap.)

Together with the previous bound, this shows that $$a(n) = \left( \frac{n-1}{2}\right)^2$$ whenever is odd, so we completely understand the odd-numbered terms of this sequence.

Getting even…

The even-numbered terms, however, seem more subtle. The integer programming approach handily deals with all cases up to , but gets a bit stuck on . It finds the following packing with tiles:

but (after running for days) it can’t quite rule out the possibility that there’s an even better solution with tiles. That being said, we do know that there’s no solution with more than tiles. This is because the integer programming solver uses a “primal-dual” algorithm which, roughly, means that as it’s performing the search it’s keeping track not only of the best solution it’s found so far (which is a lower-bound for the value of ) but also the best solution to the “dual” version of the problem (which, it turns out, is an upper-bound for the value of ). And the search did find a “dual” solution that was strictly smaller than , so we know that .

So, even in cases when the algorithm doesn’t find the optimal solution, it can give us useful bounds on the optimal solution. This is another reason why the integer programming approach is particularly appealing for this kind of tiling problem.

After , the next “hard” case is , where we know that $$163 \leq a(26) \leq 165,$$ but we don’t know the exact value. Similarly for other even we have upper and bounds, but don’t (yet) know the exact values.

Going Further

Undoubtedly, as computers get faster and as even better integer programming solvers are developed, we’ll come to learn the true values of and other terms of A355477. (Some readers may even have access to “industrial grade” (mixed) integer programming solvers that can already solve the instances that stumped the open-source tools I used…) And perhaps there are some clever mathematical insights that will lead to a better understanding of the even terms of this series. Time will tell!