Creating a tiling algorithm for a given space

Question

We have to create an algorithm to fill up a given space of HxW perfectly. We have 125 test configurations with a given tile set that can fill up the field. The code for the tile set and the field is given and we have to write a code that can place the tiles and fill up the field(you can swap them if necessary). Does someone have suggestions on how to create such an algorithm because we are stuck and have no inspiration left.

We created a greedy algorithm that fill's up the largest tiles first and then tries to fit in the small ones but this has only solved 1 tile set and get's stuck with the larger tile sets.

Underneath are 2 given configurations:

width: 12 height: 17 scale: 20 2 times 5x5 1 times 7x3 3 times 5x4 1 times 5x3 1 times 6x2 1 times 3x3 2 times 4x2 1 times 6x1 1 times 3x2 1 times 2x2 1 times 3x1 1 times 2x1

width: 42 height: 39 scale: 10 1 times 15x14 1 times 14x14 1 times 14x8 1 times 11x9 1 times 12x6 1 times 14x5 1 times 11x6 1 times 16x4 1 times 12x5 1 times 10x5 2 times 8x6 2 times 8x5 1 times 9x4 1 times 6x6 1 times 7x5 2 times 6x5 1 times 7x4 1 times 6x4 1 times 10x2 1 times 5x4 3 times 6x3 2 times 7x2 1 times 12x1 2 times 6x2 1 times 11x1 1 times 10x1 1 times 5x2 1 times 8x1 1 times 6x1 2 times 3x2 1 times 5x1 2 times 2x2 3 times 3x1 3 times 2x1 1 times 1x1

Answer 1

Of course, it being an NP-hard problem (NP-complete if you only want to know whether it's possible, but it seems like you're already promised this and anyway you want some configuration) is not purely a bad thing - while it means it's probably not going to be overly efficient, it also suggests lots of angles of attack, so this doesn't have to be approached from scratch.

For example Integer Linear Programming, with a model such as (well this is a pretty basic one)

minimize: 0
subject to:
for all (x,y), sum[all i such that tp[i] covers (x,y)] x[i] = 1
for all tiles k, sum[all i such that tp[i] is tile k] x[i] = 1

Where tp contains all the possible "tile-placements", with a copy of every time for every location it can be in.

The first batch of constraints forces all positions in the grid to be covered by a tile, the second bath of constraints forces all tiles to be used exactly once.

Using this I could solve your 42x39 instance:

More tricks may be necessary for larger instances. Some of the cuts mentioned here apply, but when I solve this with Gurobi it spends most time to find a feasible solution, not so much in the integer phase.