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

This problem is NP-Complete. Even in 1D (1Xm board), this is equivalent to subset sum problem. — amit, Jan 24 '16 at 17:30
There is a known problem called subset-sum problem. The problem is: Given a set of numbers, is there a subset of them that sums to some target sum. If you have 1xM board, and some tiles, if you had a polynomial time algorithm to solve your problem, you could solve subset sum polynomially as well, but there is no known algorithm (and most believe such does not exist). There is *pseudo polynomial* time algorithm to subset sum, but I am not familiar if it has a modification that works for 2D, and I suspect 2D is strongly NP Hard. — amit, Jan 24 '16 at 17:35
@amit I was under the impression that all the tiles will definitely exactly fill the board, not a strict subset of them. It's not like subset sum then, the 1D case is trivial (just fill it up from one end). 2D case is still probably hard but I'm not sure what it's equivalent to — harold, Jan 26 '16 at 11:41
@harold Even with that assumption, the problem is NP-Hard with reduction from partition problem. (find two subsets that each sums to half the total sum). In here, you again map every item `x` to (1,x) and your board is of size 2xsum/2 — amit, Jan 26 '16 at 17:19

score 1 · Answer 1 · edited May 23 '17 at 12:04

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.

Creating a tiling algorithm for a given space

1 Answers1