The Problem

I need to pack the maximum number of packages on a 2 dimensional grid. Think of a chess / checkers like grid. One square can only accommodate one package.

The packages come in groups of 3 to 8, and have some requirements:

• The group has to be completely placed on the grid (partial placement is not an option)
• There is a required pattern for each group. The requirement tells you how many sub-groups the packages need to go in, the size of each sub-group and the minimum “gap” between sub-groups.

I have an existing solution in place which “molds” the incoming groups based on the space available. That approach works very well until I get to the end. Which is where I need some help devising an algo.

An Example

Let’s say this is the current state of the grid. The existing packages all satisfy their respective constraints. Now I need to place a group of 3 pieces in 2 sub-groups with a minimum gap of 2 (something like 2,0,0,1). I can obviously not place the incoming group on this grid.

X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X . . . X X

I could move the existing pieces to make room like this:

X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
X . X X X X X
X . X X . X X

Or this

X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X . . X X .

Or this

X X X X X X X
X X X X X X X
X X X X X X X
X X X X X X X
. X X X X X X
. X X X X X .

There are of course many combinations that would work. I just need to get to one of them.

The Ask

I would love to know if this is (or can be modeled as) a well known problem with a known solution. But I’ll take any logic that works. It is desirable to move as few pieces as possible, but I don’t need the “best possible” option. “Good enough” would do.