[Math] How to find the smallest square possible, out of Tetris pieces

algorithms

I need to arrange an uncertain number of Tetris pieces, into the smallest possible square. The pieces I get are static, so I am not allowed to turn them and the square is allowed to have holes inside.

I am supposed to write a program to do this, but I think this is more of a mathematical problem.

In total, there are 19 different possible pieces. I thought of starting to create the minimal square, in case all the pieces fit in perfectly.

The equation would be: $m = \sqrt{n\cdot 4}$ rounded up, with m being the minimal size and n being the number of pieces you have. All the pieces are typical Tetris pieces made out of 4 combined blocks.

My idea now was to try to fit all pieces into this square, and enlarge it by 1 if it doesn't fit. The obvious problem now is the algorithm, to place the pieces in the best way possible. For doing that I only came up with the idea to define certain pieces, which combine to a rectangle together. I the program would find all the pieces needed for this rectangle, it would know how to continue with those pieces.

This would actually work with some examples, but there are also a lot of possible combinations, where the smallest square possible wouldn't even contain one rectangle inside.

If anyone has an idea how to solve this, I'd really appreciate the help.

Edit: I am looking for an algorithm that actually places the pieces in the square.

Best Answer

This is not an answer, just an illustration that the largest square necessary is $9$ x $9$ as it can enclose all $19$ Tetris pieces. Done manually, I'm afraid.

Related Solutions

[Math] Covering area algorithm

I cannot remark on "the unique feature of being able to exclude some possible center points of rectangles," a feature I do not understand. But I can offer some pointers to algorithms for covering with rectangles. First, an optimal cover is NP-hard: Culbertson and Reckhow, "Covering polygons is hard," 1988. Second, there are nevertheless published approximation algorithms: Berman and Dasgupta, "Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems," 1994; Ramesh and Ramesh, "Covering Rectilinear Polygons with Axis-Parallel Rectangles," 1999. And you could use Google Scholar to find all later papers that reference these. Perhaps some of these algorithms can be adapted to include your unique features.

Algorithm for Maximum Size of Squares in a Rectangle

Let's analyze a single case:

If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.

So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$

So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$ Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$

If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$

Let's now recall the formulas we had.

We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.

A better method:

Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that $$a=x/p_x$$ where $a$ is the value of the actual side of our squares. Then we know that for our side to fit we need to reduce it: $$S_x=y/(\lceil y/a \rceil)$$ We do the same with $S_y$ and calculate $max(S_x,S_y)$ The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.

Plain, unoptimized C Code

Some multiplications may be reused but for code readability and practical uses this is enough. Input: values of $x$,$y$, and $n$. Handcoded.

Output: The optimal side of our squares

#include <math.h>
#include <stdio.h>
#define MAX(x,y)    (x)>(y)?(x):(y) 
int main(){
    double x=5, y=6, n=7;//values here
    double px=ceil(sqrt(n*x/y));
    double sx,sy;
    if(floor(px*y/x)*px<n)  //does not fit, y/(x/px)=px*y/x
            sx=y/ceil(px*y/x);
    else
            sx= x/px;
    double py=ceil(sqrt(n*y/x));
    if(floor(py*x/y)*py<n)  //does not fit
            sy=x/ceil(x*py/y);
    else
            sy=y/py;
    printf("%f",MAX(sx,sy));
    return 0;
}

Related Question