0

I currently have a square, and a series of rectangles of the following sizes: (225,300), (225,450), (450,225), (300,225)

I need to design an algorithm that determines all possible combinations of blocks in this square without overlapping, always filling the entirety of the box and assuming there are infinite amounts of each block. Are there any algorithms that currently handle this in an efficient way?

amit
  • 175,853
  • 27
  • 231
  • 333
user293895
  • 1,465
  • 3
  • 22
  • 39
  • 2
    Let's see, you can divide the dimensions by 75, since all the dimensions of the smaller bricks are divisible by 75. Then you have 2 types of smaller bricks, 3,4 and 3,6 (can be rotated). I think finding the combinations can be done with DP (?) – nhahtdh Dec 25 '12 at 09:07
  • 2
    The number of combinations grows exponentially: Two long boards form a square; if the board is 6x6, there are already two placements. If the board is 12x12, there are more then 16 placements. For an 18x18, that's more than 512 placements. For a 24x24, that's more than 65k. – John Dvorak Dec 25 '12 at 09:08
  • 1
    Do you need to list all the possible combinations, or just count how many there are? As Jan Dvorak says, listing them will take exponential time. – interjay Dec 25 '12 at 09:29
  • I do need to list all possible combinations. I wouldn't worry about the exponential amount of time, in the real world application of this algorithm (separating chunks from parking signs) the size of the square will be constrained. I realise that this means I could define all possible combinations for my constrained sizes but I'd rather use this approach. – user293895 Dec 25 '12 at 09:45

2 Answers2

3

In the literature, efficiently = polynomially.

Note that even if you know you can fill the square completely - finding ALL the possible ways to do it is exponential, since there are exponential number of those.

Have a look on a 6K * 6K board. One way to fill it is to reduce it to K^2 subsquares all of size 6*6, for each of these you can either use (6,3) or (3,6) to create it - resulting in 2^(K^2) possible ways to fill the square. (and we still didn't cover all possible ways to do it).

Thus, generating ALL solutions cannot be done polynomialy (=efficiently).
I would go for some backtracking / exhaustive search solution to check all possible placemenets to get the desired result.

Original answer, disregards some issues in the specific problem, and facing a more general variation of it (the board given is a rectangle, not a square, the tiles are not fix sizes):

However, the problem of determining if there is any possible way to fill a square rectangle1 completely is NP-Hard, A private case of it (Given a "board" and one possible rectangle of size nxm) is discussed in this thread, and is proved to be NP-Hard, thus there is no known polynomial solution for this problem.

Since determining if there is any possible tiling is NP-Hard, finding all of them (or even one of them) cannot be done polynomially as well (unless P=NP, but most consider it unlikely).

(1) The original answer writes square but assume rectangle. For squares it might be easier to find a single answer, and the reduction does not hold.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • Thanks, this is what I ended up doing, the solution is here: https://github.com/8W9aG/BlockPlacement – user293895 Dec 25 '12 at 14:41
  • In this case only (pointed out in ChengYi He's answer), since the unit tiles' areas are divisible to 6 and the space to fill is a square, the only candidate are N = 6k. And N = 6 is fillable, so any N = 6k are fillable. I think this is a special case that doesn't necessarily fall under NP-Hard. Or am I wrong somewhere? – nhahtdh Dec 25 '12 at 16:10
  • 1
    @nhahtdh: The logic behind my answer fails for squares, I was thinking of general rectangles. I would have deleted it - but you cannot delete an accepted answer :| Anyway, finding ALL possible ways to do it still cannot be done efficiently because you still have exponential number of answers (only if you divide your problem into subsquares of 6x6 - you have 2 possibilities per square, and we still missed a lot of possibilities. I'll try to clarify this issue. – amit Dec 25 '12 at 16:17
1

We could solve this problem if only the four kinds of rectangles are used to fill the square.

Input: N
Output: Determine if the square with dimension N could be filled with the rectangles (3,4), (3,6), (6,3), and (4,3).

The answer is true if and only if

  1. N is positive integer
  2. N mod 6 == 0

Following goes my explanation.

  1. N should be integer because we couldn't get fractions with additions of integers.
  2. If N mod 6 == 1, then the area of this square mod 6 == 1.
    If N mod 6 == 2, then the area of this square mod 6 == 4.
    If N mod 6 == 3, then the area of this square mod 6 == 3.
    If N mod 6 == 4, then the area of this square mod 6 == 4.
    If N mod 6 == 5, then the area of this square mod 6 == 1.
    Since the areas of each given rectangle is multiples of 6. It's impossible to fill these squares with these rectangles.
  3. If N mod 6 == 0, then we could fill this square with (3,6) or (6,3).