Placing tetrominos in square, maximum size

Question

I am currently coding an algorithm which places a list of Tetrominos (tetris pieces) in the smallest square possible.

My question is : is there a mathematical way to know the maximum size (upper bound) of the square knowing that :

• Tetrominos consist of 4 squares, each one being adjacent to at least 1 other one

• I do not get to rotate the Tetrominos

• The square can have holes, it does not get to be perfect

For now I assumed that max_size = min_size + 2, where min_size = sqrt(nbr_pieces * 4) (rounded up), but I do not see how to prove it right or wrong.

PS : as it is my first post in this forum, please tell me if I need to change tags for this question

Answer 1

No, because there is no maximum size that works for all combinations of tetraminoes.

If you have two T-tetraminoes in the same orientation, you need a $4 \times 4$ square to fit both, but if you have two L-tetraminoes with opposite rotations, you only need a $3 \times 3$ square.

Answer 2

I think you are right on target with an upper bound of $\lceil2\sqrt n+2\rceil$. The only possible improvement would be to allow proper rounding, which would be $\lfloor2\sqrt n+2.5\rfloor$. I'm fairly certain that this is a safe improvement.