Squaring the square

This is a challenging puzzle and there is unfortunately no clever trick one can use to solve it quickly. If we consider the general problem of tiling an $N\times N$ grid using smaller squares, we can make several observations:

• The smallest answer we could ever hope for is $4$. If $N=2k$ is even, we can achieve the minimum by splitting the square into four $k\times k$ squares. It’s clear that this solution cannot be improved.
• If $N = 3k$ is a multiple of $3$, we can split it into six pieces: one $2k\times 2k$ square and five $k\times k$ squares. I believe this also cannot be improved.
• When $N$ has many divisors, it becomes easier to tile it. The most challenging cases are therefore the cases where $N$ is prime. So a larger grid doesn’t necessarily mean a more difficult problem! We’ll see examples of this later.

I’ll solve this problem by converting it into an integer linear program (specifically, a variant of a knapsack problem), which can be solved much more efficiently than by brute-force checking the astronomical number of possible tilings.

I’ll illustrate the approach for the $5\times 5$ case. We’ll represent each possible square as a $5\times 5$ matrix of $0$’s and $1$’s. For example, we can use $25$ different $1\times 1$ tiles:
\[
\scriptsize \begin{bmatrix}{\color{red}{\color{red}1}}&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&{\color{red}1}&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&0&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},\,\dots\,,
\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&{\color{red}1}\end{bmatrix}
\]We can also use $16$ different $2\times 2$ tiles:
\[
\scriptsize \begin{bmatrix}{\color{red}1}&{\color{red}1}&0&0&0\\{\color{red}1}&{\color{red}1}&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&{\color{red}1}&{\color{red}1}&0&0\\0&{\color{red}1}&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},
\begin{bmatrix}0&0&{\color{red}1}&{\color{red}1}&0\\0&0&{\color{red}1}&{\color{red}1}&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix},\,\dots\,,
\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&{\color{red}1}&{\color{red}1}\end{bmatrix}
\]Continuing in this fashion, we have $9$ different $3\times 3$ tiles and $4$ different $4\times 4$ tiles. So in total, we have $25+16+9+4=54$ different tiles. The name of the game is to pick the smallest possible subset of these matrices that sums to the matrix of all $1$’s. We can represent this compactly by vectorizing each of the $54$ matrices above into $25\times 1$ columns, and then stacking the columns side by side to form a matrix $A \in \{0,1\}^{25\times 54}$. Our goal is then to solve the problem:
\begin{align}
\underset{x \in \{0,1\}^{54}}{\text{minimize}}\qquad& \sum_{i=1}^{54} x_i \\
\text{subject to:}\qquad & Ax = 1
\end{align}Here, each $x_i$ is a binary variable that selects whether we’ll be using the $i^\text{th}$ column of $A$ or not. It turns out the optimal solution for this $5\times 5$ case uses $8$ squares; or the sum:
\begin{multline}
\scriptsize \begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\{\color{red}1}&{\color{red}1}&{\color{red}1}&0&0\\{\color{red}1}&{\color{red}1}&{\color{red}1}&0&0\\{\color{red}1}&{\color{red}1}&{\color{red}1}&0&0\end{bmatrix}
+\begin{bmatrix}{\color{red}1}&{\color{red}1}&0&0&0\\{\color{red}1}&{\color{red}1}&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&{\color{red}1}&{\color{red}1}\\0&0&0&{\color{red}1}&{\color{red}1}\end{bmatrix}\\
\scriptsize+\begin{bmatrix}0&0&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&{\color{red}1}&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&{\color{red}1}&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
+\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&{\color{red}1}\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}
\end{multline}This general strategy of enumerating choices and then selecting among them doesn’t scale all that well because as $N$ gets large $A$ grows pretty quickly. In fact, $A$ will be $N^2 \times \tfrac{1}{6}(N-1)(2N^2+5N+6)$. However, in these cases we can use a heuristic such as column generation to quickly obtain approximate answers that can be iteratively and efficiently refined.

I solved the above integer linear program using Julia with JuMP and the Mosek solver. Read ahead for the results!

Here is what I found for the first few odd values of $N$ (remember, the answer is just $4$ when $N$ is even!):

Most of the cases solve in a matter of seconds. The slowest case was $23\times 23$ ($4323$ binary variables, $529$ constraints) and it took about $45$ seconds. As observed before, the solution is $6$ whenever $N$ is a multiple of $3$, and the solutions get more intricate when $N$ is prime. Of course, we don’t need to restrict ourselves to square boards! Here are some examples of optimal non-square tilings:

Some observations:

• Using even numbers doesn’t necessarily lead to simple solutions when the canvas isn’t square!
• Using sidelengths that are consecutive Fibonacci numbers (e.g. the 8×13 case above) leads to the famous approximation of the Golden spiral. Perhaps not surprising, but still very cool!

If you’d like to read more about the “squaring the square” problem and its long history, check out the Wiki article on it!