CODEWITHSUNDEEP
algorithm
Greg Weber
Greg Weber

Reputation: 3428

tile arrangement algorithm

I need to arrange square tiles of the same size in a space that could be completely full of the tiles. Some tiles may be locked in place. Tiles come from groups, and each group should be located together (if possible, may not be due to locking). There are also some other secondary and more individual (not just by group) preferences.

What algorithms would be useful? I am trying to turn this into a linear (well MIP actually) programming problem, but I am not sure if I can accomplish that.

Upvotes: 1

Views: 2044

Answers (1)

Antti Huima
Antti Huima

Reputation: 25522

Combinatorial optimization problems (if you want to "maximize" the fit to the secondary and more individual preferences) can be typically solved by branch-and-bound or by stochastic search, e.g. simulated annealing or tabu search.

In branch-and-bound, you search through partial solutions, and keep track of the best complete solution reached so far. Whenever you reach a partial solution where you can prove that it can't be completed to get a better solution than the best solution so far reached, you backtrack immediately.

Stochastic search would most likely be a better fit to your problem. It works by starting with a random tile placement, and then e.g. swapping to tiles randomly, put preferring moves that lead to higher satisfaction (higher preference score), which in your case would mean more connected tiles and more fit to the secondary preferences. The details differ. See

Upvotes: 3

Related Questions