## Maximal squares of polyominoes

Given a set of polyominoes, say the heptominoes, which is the largest square we can cover with them?

The problem is trivial for the monomino and impossible for the domino and for the triominoes. For the tetrominoes the only possible (unsatisfactory) solution is given by the Q tetromino itself, since there is no way to form a 4×4 square using 4 of the 5 tetrominoes.

Things become more interesting for pentominoes, hexominoes and heptaminoes. The maximal squares, that you can see below, have sides 5, 12 and 21, respectively.

Enter the octominoes. Here things get tougher, at least for my limited means... With some efforts I was able to tile two maximal squares: the 52×52 that uses 338 octominoes and the 53×53 which, stretching a little the rules, uses 351 octominoes one of which has a hole in the center:

It should be possible to pack 1225 nonominoes in a 105×105 square, but for the moment I was unable to obtain this tiling.

This short gallery of results is aptly closed by the Livio Zucca's masterpiece: a 210×210 square made of 4410 decominoes! I reduced (and 4-colored) the picture below, but you can also see the larger, BN, original picture.

To obtain this remarkable result, Livio adopted a mixed strategy: he wrote a program which added dekominoes to the scheme according to a clever ordering until it reached a blind alley. At that point Livio manually adjusted some pieces and the program could continue its work. After several (dozens of) man-machine iterations the remaining hole to be tassellated was small enough to be managed by a standard polyomino solver.