algorithm - Optimal tiling of polygon using ArcGIS Desktop?

I am trying to tile a polygon with a minimal number of fixed sized squares.

Currently I am creating a fishnet over my polygon then spatially joining the squares that intersect the polygon. This is not optimal.

Also note the squares can be shifted vertically/horizontally but not rotated.

My end goal: The polygon represents a clipped image and I want a tiling of the clipped image. Where each tile is 300px by 300px. Some overlap is fine if that makes the problem easier.

Current

Manually optimized

Are there any tools or algorithms that would help with this? I am proficient with Python and ArcMap.

The polygon was created from line features so I also have access to those segments. Maybe that would will help for generating the squares.

The entire polygon must be covered.