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

  • $\begingroup$ Calculus was a bad tag, because that is, crudely speaking, about differentiating and integrating functions. More experienced users will often happily edit tags. I'm not 100% my choices are best possible, but IMO they are closer to the mark :-) $\endgroup$ – Jyrki Lahtonen Jan 21 '16 at 13:27

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.

  • $\begingroup$ Of course, and I expect my function to return 5 for n = 2 (as you need a 5 x 5 square to fit two I-tetraminos, but I guess there should be ways to get an upper bound for a given number of tetraminos. $\endgroup$ – realUser404 Jan 21 '16 at 14:29
  • $\begingroup$ @realUser404: Why do you say that two I-tetraminoes need a $5 \times 5$ square? Just $4 \times 4$ will do. $\endgroup$ – user21820 Jan 21 '16 at 14:41
  • $\begingroup$ If one is vertical and the other one horizontal, then 5 x 5 is needed $\endgroup$ – realUser404 Jan 21 '16 at 14:48
  • $\begingroup$ @realUser404: Right; I don't know how I missed that... The problem is that there are simply too many cases to reliably check all by hand. Clearly it is relevant that each tetramino individually can tesselate the plane, and so the rough edges between different tetramino clumps is all that matters. $\endgroup$ – user21820 Jan 21 '16 at 14:50

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.

  • $\begingroup$ Thank you for this answer, but can you also explain how you got to this result? $\endgroup$ – realUser404 Jan 21 '16 at 16:53
  • $\begingroup$ @realUser404 It was just an observation. The first difference is for $n=3$. The improved upper bound is 5, and as far as I can tell, any 3 tetrominos can be arranged in 5x5 square. $\endgroup$ – Logophobic Jan 21 '16 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.