# Tiling a rectangle with the fewest squares

Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.

Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best known algorithm?

• @AndrásSalamon A $5 \times 6$ rectangle is a counterexample for the optimality of Euclid's algorithm. Aug 2 '13 at 11:03
• Already asked here: mathoverflow.net/questions/44524/…, some interesting pointers are given. Aug 2 '13 at 14:31
• Minimum number of integer-sided squares needed to tile an m by n rectangle from The On-Line Encyclopedia of Integer Sequences. oeis.org/A219158 Aug 2 '13 at 15:18
• Let $h(n,m)$ be the minimum number of integer-sided squares that tile an $(n,m)$ rectangle, if $k\geq2, 0\leq d <n$, do you know if this equation always holds: $h(n,kn+d) = (k-1) + h(n,n+d)$? (i.e. can we greedily remove k-1 $n\times n$ squares and reduce the problem to tiling an "almost square" with squares?) Aug 2 '13 at 22:47
• @MarzioDeBiasi There is a counterexample for this equation: $h(2 \cdot 53 + 6,53) = h(53 + 6,53) = 11$ (see int-e.eu/~bf3/squares). Aug 7 '13 at 4:43