The question is based on fragmentation in a grid and its complexity. Given a grid with some occupied blocks as shown in the figure below.
Here, each colored block is one entity and can move horizontally anywhere in available blocks. For example the block entity B at ((2,5), (2,3)) can move 7 places.
Now, to compute the fragmentation in a given grid, I consider the maximum number of contiguous available blocks for each block entity. This would mean that for entity A, currently 4 contiguous available slots exist. For B-8, C-4, D-5, E-6, F-4.
With the given grid, we are now allowed to shift any entity to any other available place but only row-wise.
Now, my aim is to shift each entity in a way such that the fragmentation is reduced. My current approach is to shift each entity iteratively and greedily maximize the number of contiguous blocks. The pseudocode for this approach is:
for each block entity: max_contiguous = 0 for each available block: Do shift and compute new contiguous blocks max_contiguous = max(max_contiguous, new_contiguous)
However, in the current approach there are many possible combinations that would not be considered since once an entity is shifted, it’s place is fixed. I am now wondering if I can find the lower bound of the fragmentation for a given grid without searching all combinations exhaustively. Essentially, I aim to shift the entities such that the max available contiguous blocks for each entity is maximized. However, I am unable to formulate a way to do this without computing all possible combinations. Any shift for one entity affects several other entities.
Any guidance/help that could direct me would be very helpful. Thank you.