Algorithm to get minimum movement to avoid square overlap

Question

I have a problem in a chemistry optimization program that is equivalent to the following question. I can't find a good algorithm for it:

Suppose I get N identical free to move squares with known initial longitudes, fixed width, and M identical "obstacles" with fixed positions.

Is there a algorithm to get a "minimum" total horizontal movements of those squares that can:

1. retain the order of squares
2. result in no overlap ("no touching") of squares and obstacle; and no overlap between squares.

The "minimum total movements" generally describes the position difference of before & after the movement. It can be the sum of deviations, or root-mean-square deviation, etc, whichever is easier.

It doesn't have to be the minimum, but a close one is desired for a good optimization.

I may have up to 50 squares and 25 obstacles, so brute-force is too slow.

I also find this post. But it doesn't work with the fixed obstacles, and doesn't necessarily kept the order of squares.

Answer 1

O(|sq|^2 * |ob|) general complexity.

ob = [1, 5, 6, 7, 10, 13]
sq = [-3, 0, 3, 6, 8, 14]

Let f(i, j) represent the best solution where squares up to sq[i] must fit to the left of obstacle, ob[j]. Solve f(i, 0) for packing 1,2,3...50 squares where the right obstacle is ob[0]. Then, extending to obstacle ob[1], the solution will be

f(i, 1) = min(
  f(k, 0) + cost of placing squares sq[k+1...i] between ob[0] and ob[1]
)
for all k

Follow through for each j.