we have create algorithm fill given space of hxw perfectly. have 125 test configurations given tile set can fill field. code tile set , field given , have write code can place tiles , fill field(you can swap them if necessary). have suggestions on how create such algorithm because stuck , have no inspiration left.
we created greedy algorithm fill's largest tiles first , tries fit in small ones has solved 1 tile set , get's stuck larger tile sets.
underneath 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
of course, being np-hard problem (np-complete if want know whether it's possible, seems you're promised , anyway want configuration) not purely bad thing - while means it's not going overly efficient, suggests lots of angles of attack, doesn't have approached scratch.
for example integer linear programming, model such (well pretty basic one)
minimize: 0 subject to: (x,y), sum[all such tp[i] covers (x,y)] x[i] = 1 tiles k, sum[all such tp[i] tile k] x[i] = 1 where tp contains possible "tile-placements", copy of every time every location can in.
the first batch of constraints forces positions in grid covered tile, second bath of constraints forces tiles used once.
using solve 42x39 instance:
more tricks may necessary larger instances. of cuts mentioned here apply, when solve gurobi spends time find feasible solution, not in integer phase.
Comments
Post a Comment