How many different ways can you place a set of squares, each with integer side length, on a 2D grid of size N x N without overlapping?

692 Views Asked by At

The question can be understood as follows:

You are given a set of $n$ different sized squares $S = \{ \left(K_1, L_1 \right), \left(K_2, L_2\right), ..., \left(K_n, L_n \right) \} $ where $K_i$ is the number of squares with side length $L_i \in \mathbb{N}$. How many different ways can you place these squares on a 2D grid of size $N \times N$ without letting the squares overlap each other and constraining the squares to be axis aligned? Gaps or spaces between squares are allowed.

I'm also interested in how allowing the squares to be some discrete number of colors may change the solution, but I think that might be asking quite a bit...


Example solutions:

  1. For the set $S = \{\left(2, 1\right)\}$ and $N = 2$, meaning we have a $2 \times 2$ grid with 2 $1 \times 1$ squares, the correct solution is 6. Graphically this solution is shown below with black denoting the squares you can place, white being empty space, and green being the border of the grid. A $2 \times 2$ grid solution given 2 $1 \times 1$ squares

  2. For the set $S = \{\left(2, 2\right)\}$ and $N = 4$, meaning we have a $4 \times 4$ grid with 2 $2 \times 2$ squares, the correct solution is 16. A $4 \times 4$ grid solution given 2 $2 \times 2$ squares

  3. For the set $S = \{\left(3, 2\right)\}$ and $N = 4$, meaning we have a $4 \times 4$ grid with 3 $2 \times 2$ squares, the correct solution is 8. A $4 \times 4$ grid solution given 3 $2 \times 2$ squares


My attempt(s) at a solution:

It is trivial for the case $n = 1$, $L_1 = 1$. For an $N \times N$ grid, you can frame this question as: How many different ways can I choose $K_1$ tiles from $N^2$ total tiles? This then leads to the simple result of the total number of different ways to lay the $1 \times 1$ tiles as $N^2\choose{K_1}$.

However, as soon as you consider the $n = 1$, $L_1 = 2$ case, I cannot find a closed form expression like the above. I have noted that for a $2 \times 2$ square, the first square can be placed in $\left(N-1\right)^2$ different ways. However, the number of different ways you can place the second square depends on where you placed the first square. I have also considered turning the grid into a $\frac{N}{2} \times \frac{N}{2}$ grid and making my squares have a new side length $L_1' = \frac{L_1}{2} = 1$ in this new coordinate system and using the same machinery to solve the $L_1 = 1$ case. However, if you place two $2 \times 2$ squares a single tile apart, this new coordinate system cannot handle this.

By studying the example problems above one can note there is some definite symmetry in the solutions. For example 1), there are two different solutions that have either a 180 degree rotation symmetry or no rotation symmetry leading to the 6 solutions. For 2), there are 5 different solutions that have these same symmetries leading to the 16 solutions and lastly 3) has 2 different elements that have no rotation symmetry and therefore gives the 8 different solutions. To me this seems that the machinery of permutation group theory might be applicable here. However, I am not sure how to identify these generators given a grid size and number of squares of some integral side length nor how to identify their symmetries.

It is not clear to me how to generalize this to the next $2 \times 2$ square size, let alone to a mixture of squares of different integer side length.

1

There are 1 best solutions below

0
On

I cannot think of a practical way to solve your general problem; as Ross Millikan noted, it is probably a very hard problem. But since you already have gotten stuck on the $n=1, L_1=2$ case I can give you some pointers how to "solve" that case (the method I propose will still be very messy if $K_1$ is 3 or greater, or even for $K_1=2$ if $L_1$ is large). The main idea is to calculate how many arrangements there are if we ignore the constraint that the squares do not overlap, and in addition calculate how many arrangements there are when the squares do overlap --- because then the difference will give us the answer we are looking for.

If $K_1=2$, it is clear that if you ignore the constraint that the squares do not overlap, and in addition overcount by labeling the squares, there are $$(N-1)^2(N-1)^2=(N-1)^4$$ arrangements which include arrangements which do have overlaps. There are exactly $(N-1)^2$ arrangements where the amount of overlap is 4 unit squares, so there is a total of $${(N-1)^4-(N-1)^2\over2!}$$ arrangements left where we do not distinguish between the two squares. Notice that is impossible that the overlap is 3 unit squares, so we are left to calculate the arrangements which have overlaps of 2 or 1 unit squares.

For an overlap of 2 unit squares, the squares can form rectangles of size either $3\times2$ or $2\times3$, and each such rectangle can be placed in the $N \times N$ square a total of $(N-1)(N-2)$ ways --- in total, we have $$2(N-1)(N-2)$$ such arrangements.

Similarly, for an overlap of 1 unit square, there are two possibilities for how the squares overlap (they form a $3\times3$ square from which two diagonally opposed corners have been removed). Each such shape can be placed $(N-2)^2$ ways, for a total of $$2(N-2)^2$$ arrangements.

Therefore, for $n=1, L_1=2, K_1=2$ we have exactly $${(N-1)^4-(N-1)^2\over2!}-2(N-1)(N-2)-2(N-2)^2={N^4 - 4N^3 - 3N^2 + 26N - 24\over2}$$ arrangements.