Tile placement algorithm

Question

I have this field of tiles which is 36 x 36 inches wide and high.

So I have blocks 8x8, 6x6, 6x8, 4x8 which can be rotated 90 degrees to fit wherever possible. My task is to make application that calulates which and how many blocks should be chosen so that all together fit in to a given wall oppening. In this example oppening 36 x 36.

Note: The oppening should be filled with as least as possible tiles, meaning bigger tiles have priority

Which algorithm should I use for tile placement?

Another example. Field 30 x 30 is drawn like this:

50 x 50

Answer 1

Since amit gave the general case answer, I'll make this one specific. With those four blocks sizes, and assuming it's even possible (dimensions are even and >= 6, etc), you can use a semi-greedy algorithm:

The first obective is to maximize the number of 8x8 blocks. To do that, you need to figure out how many 6 size blocks you need in each direction. For each dimension, just check for divisibility by 8. If it's not divisible, subtract 6. Repeat until divisible (it shouldn't take more than 3 tries).

However many times it took, that's how may 6x6 blocks you need in that dimension. Form a rectangle out of them and put it in one corner. Form another rectangle out of 8x8 blocks and put them in the opposite corner. The corners of these two rectangles should be touching.

So now you probably have some leftover space, in the form of two rectangles in the opposite corners. We know that one dimension of each is divisible by 8, and one is divisible by 6. The easy way out here would be to fill it up with 6x8 blocks rotated appropriately, but that doesn't guarantee the maximum number of large(8x8) blocks. For example, with 50x50, you'd have two rectangles of 18x32 left. You could fill them with twelve 6x8 tiles each. You can't even do better than 12 blocks each, but you can fit more 8x8 blocks in there.

If that's not a concern, then you're done (hooray). The bonus this way is that you never need to use the 4x8 blocks.

---

If you do want to maximize the 8x8 blocks, you'll have to take another step. We're concentrating on the dimension divisible by 6 here, because the 8 is easy. Every size we might need(8x8,6x8,4x8) stacks there perfectly.

For the other side, there are only 3 possible numbers that it could be: 6, 12, and 18. If it's anything else, the first step wasn't done right. Then take the following action:

• For 6, add a row of 6x8 (no optimization)
• For 12, add a row of 4x8 and a row of 8x8
• For 18, add a row of 4x8, a row of 6x8, a row of 8x8

Done!

---

To see the difference, here we have two 50x50 grids:

Blue  - 8x8
Red   - 6x6
Green - 6x8
Gray  - 4x8

This first example gives us 49 total blocks. The blue is a 32x32 area (16 blocks), red is 18x18 (9 blocks), and the rest is simply filled with 6x8's (24 blocks).

This example still gives 49 total, but there are more 8x8 blocks. Here we have 24 large blocks, rather than 16 in the last example. There are now also 4x8 blocks being used.

Answer 2

Here you go, in Python:

def aux(x):
    # in h we store the pre-calculated results for small dimensions
    h = {18:[6,6,6], 16:[8,8], 14:[8,6], 12:[6,6], 10:[6,4], 8:[8], 6:[6], 4:[4]}
    res = []
    while x > 18: 
        # as long as the remaining space is large, we put there tiles of size 8
        res.append(8)
        x -= 8
    if x not in h:
        print("no solution found")
        return []

    return res + h[x]

def tiles( x, y ):
    ax = aux(x) # split the x-dimension into tiles
    ay = aux(y) # split the y-dimension into tiles
    res = [ [ (x,y) for x in ax ] for y in ay ]
    for u in res:
        print(u)
    return res


tiles( 30, 30 )

The basic idea is that you can solve x and y independently, and then combine the two solutions.

Edit: As Dukeling says this code happily uses 4x6 and 4x4 blocks, contrary to the requirements. However, I think it does that only if there is no other way. So if the results contains such blocks then there is no solution without those blocks. And if you have no Python readily available, you can play with this code here: http://ideone.com/HHB7F8 , just press fork right above the source code.

Answer 3

Assuming you are looking for general case answer, I am sorry to say - but this problem is NP-Complete. It is basically a 2D variation of the Subset Sum Problem.

The subset sum problem: Given a set S and a number x - find out if there is a subset of S that sums to x.

It is easy to see that by reducing the subset sum problem to a "field" of size 1*x and for every s in S we have a tile 1*s - a solution to one problem is also a solution to the other one.

Thus - there is no known polynomial solution to this problem, and most believe one does not exist.
Note however, there is a pseudo-polynomial dynamic programming solution to subset sum that might be utilized here as well.