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:<\/p>\n

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\u2019s clear that this solution cannot be improved.\n<\/li>\n

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.\n<\/li>\n

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\u2019t necessarily mean a more difficult problem! We\u2019ll see examples of this later.\n<\/li>\n<\/ul>\n
I\u2019ll solve this problem by converting it into an integer linear program<\/a> (specifically, a variant of a knapsack problem<\/a>), which can be solved much more efficiently than by brute-force checking the astronomical number of possible tilings.<\/p>\n
I\u2019ll illustrate the approach for the $5\\times 5$ case. We\u2019ll represent each possible square as a $5\\times 5$ matrix of $0$\u2019s and $1$\u2019s. For example, we can use $25$ different $1\\times 1$ tiles:
\n\\[
\n\\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},
\n\\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},
\n\\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\\,,
\n\\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}
\n\\]We can also use $16$ different $2\\times 2$ tiles:
\n\\[
\n\\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},
\n\\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},
\n\\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\\,,
\n\\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}
\n\\]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$\u2019s. 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:
\n\\begin{align}
\n\\underset{x \\in \\{0,1\\}^{54}}{\\text{minimize}}\\qquad& \\sum_{i=1}^{54} x_i \\\\
\n\\text{subject to:}\\qquad & Ax = 1
\n\\end{align}Here, each $x_i$ is a binary variable that selects whether we\u2019ll 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:
\n\\begin{multline}
\n\\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}
\n+\\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}
\n+\\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}
\n+\\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}\\\\
\n\\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}
\n+\\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}
\n+\\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}
\n+\\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}
\n\\end{multline}This general strategy of enumerating choices and then selecting among them doesn\u2019t 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<\/a> to quickly obtain approximate answers that can be iteratively and efficiently refined.<\/p>\n
I solved the above integer linear program using Julia<\/a> with JuMP<\/a> and the Mosek<\/a> solver. Read ahead for the results!<\/p>\n<\/div>\n
And here is the tl;dr, just the solutions!
\n [Show Solution]<\/a><\/p>\n
\n
Here is what I found for the first few odd values of $N$ (remember, the answer is just $4$ when $N$ is even!):<\/p>\n
$\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ $\"\"$ <\/p>\n
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\u2019t need to restrict ourselves to square boards! Here are some examples of optimal non-square tilings:<\/p>\n
$\"\"$ $\"\"$ $\"\"$ $\"\"$ <\/p>\n
Some observations:<\/p>\n
- Using sidelengths that are consecutive Fibonacci numbers<\/a> (e.g. the 8\u00d713 case above) leads to the famous approximation of the Golden spiral<\/a>. Perhaps not surprising, but still very cool!\n<\/li>\n<\/ul>\n
  If you\u2019d like to read more about the \u201csquaring the square\u201d problem and its long history, check out the Wiki article<\/a> on it!<\/p>\n<\/div>\n
  <\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"
  This Riddler puzzle is about tiling a square using smaller squares. You are handed a piece of paper containing the 13-by-13 square shown below, and you must divide it into some smaller square pieces. If you are only allowed to cut along the lines, what is the smallest number of squares you can divide this … Continue reading “Squaring the square”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2034,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[30,27,26,2],"class_list":["post-2024","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-integer-programming","tag-linear-programming","tag-optimization","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2024","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2024"}],"version-history":[{"count":12,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2024\/revisions"}],"predecessor-version":[{"id":2059,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2024\/revisions\/2059"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2034"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2024"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2024"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2024"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}