CODEWITHSUNDEEP
algorithm
user293895
user293895

Reputation: 1527

Block Placement Algorithm

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?

Upvotes: 0

Views: 1559

Answers (2)

amit
amit

Reputation: 178521

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.

Upvotes: 3

user1678380
user1678380

Reputation:

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).

Upvotes: 1

Related Questions