Problem Definition

For a 0-1 image in pixel shape of MxN and a given integer A, a feasible solution of the problem is defined as a certain number of AxA shape of pixel squares whose union may cover all of the 1-pixels in MxN image, in which the edges of the squares are parallel to edge of MxN image and aligned to pixels.
For all of the feasible solutions, I need to find any one of it who contains minimum number of squares.

What I want to ask is, is there any algorithm that may solve such problem or similar problems? Or, any suggestions about the region(Computer Vision? or Discrete Optimization?) I can seek for the algorithm I want?

Example of feasible solution

Problem Set

• M = N = 25, A = 15
• The to-be-covered area is colored with grey in the image below

Feasible Solution

• Three squares covering part of the area, colored with higher saturation.
• And the union of the squares, covering all of the grey pixels
• So the three squares make up a feasible solution of the problem, and actually its also one of the optimal solution.

Other Information

• The to-be-cover area is almost definite to be not convex, but connected.
• Actually I don’t need a policy to find the mathematical optimal solution. I’d prefer a policy that may find a good enough, almost feasible solution in limited time/complexity.