Polyominos packing into a square

Question

Rules of the game:

• Take a square grid nxn.
• Populate the grid with polyonimoes of area size 1 to area of 9.
• Polyominoes can be any shape.
• There must be one each of every size polyomino in every row and column of the grid and only once each.
• You can use as many of each size polyomino that you wish.

The image show some shapes of the smaller polyominoes

The question is

what is the smallest nxn square that can fit all of the above?

How many of each size polyomino is required?

Answer 1

First, let's establish a lower bound on $n$.

A polyomino with an area of $k$ squares can cover at most $k+1$ rows and columns. This is because a polyomino is a connected region, and if you add a square to the polyomino to enlarge it, it may expand but only in at most one direction, encroaching on just one additional row or column. A monomino covers $2$ ($1$ row and $1$ column) so a $k$-omino covers at most $k+1$ rows/columns.

For each $k\in\{1,2,...,9\}$, we need the $k$-ominos to cover the $2n$ rows/columns of the $n\times n$ board. Each one covers at most $k+1$, so we need at least $\lceil \frac{2n}{k+1} \rceil$ of them. Adding together their total area, we find that it exceeds $n^2$, the area of the board, for all $n<15$.

So we have a lower bound of $n=15$. Here is a table of the amounts in this case, and it turns out that the pieces would have to completely fill the board:

   k  #pcs  Area
   1  15    15
   2  10    20
   3  8     24
   4  6     24
   5  5     25
   6  5     30
   7  4     28
   8  4     32
   9  3     27
           ---
    Total: 225

This initial lower bound can be improved upon.

With a large polyomino you have some leeway in how many rows/columns it will cover. For example, the 9-omino can cover just 6 rows/columns if it is a 3x3 square, or 10 rows/columns when it is straight. Smaller polyominoes are less flexible.
The domino always covers exactly 3 rows/columns. For this puzzle that means that $2n$ is a multiple of $3$, and hence that $n$ is a multiple of $3$.
Similarly, the tromino always covers exactly 4 rows/columns, whichever shape it is. This means that $2n$ must be a multiple of $4$, and hence that $n$ is even.
Given these last two requirements, the smallest board size that might work is $n=18$.

Here is a solution which is highly likely to be non-optimal. I hope others can find a solution that attains the lower bound established above.

Here $n=24$. It is easy to use a $k$-omino to cover all the rows/columns of a $3\times3$ or $2\times2$ square. I combine some of these so as to make four kinds of $6\times6$ square such that each row/column is covered by the $k$-ominos being used. I then combine these four types of $6\times6$ square so that each row/column has one of each type.

Edit: Retudin has found a solution that does attain the lower bound, and which is therefore optimal.

Answer 2

The optimal answer:

Each row and column must be uniquely covered by each size
- the size 2 pieces always cover 3 (row+column)s.
- the size 3 pieces always cover 4 (row+column)s.
Thus row+column must be a multiple of 12.
- A 6x6 square cannot contaim all sizes since that needs at least 45 squares
- A 12x12 square cannot cover every row+column since that needs at least 3 of every size (135 squares) and at least one extra of size1-6 (+21 together >144)
- A 18x18 square is possible - and thus optimal (see picture)

18x18 cannot be fully packed - The solution above has 9 holes and only the fives and sixes can be more densely packed (5 i.s.o. 6 (row +column)'s )
- Since the 1,2 and 3s cannot be less dense packed, we need at least 3 extra 5s or 6s.
- 8 fives or sixes are thus needed which use at least 40 rows+columns.
- we have only 36, so overlap cannot be avoided

24x24 or greater can also not be fully packed
- the most dense packing (3x3 for 7,8,9 3x2 for 6,5 etc) has:
(9+8+7)n/6 + (6+5)n/5 = (4+3)n/4 +2n/3+ n/2 blocks (and nxn/4 places)
(where n is rows+columns.)
Which means the following must be true (4+ 2.2 + 1.75 + 2/3 + 0.5) > rows/2
thus rows < 18.233.