The way I created the pictures in my comment is by Integer Linear Programming, specifically the following model:
$\text{minimize } x \cdot area \\
\text{for each red cell } (i,j): \: \sum_{k \in covers(i,j)} x[k] \ge 1 \\
x \in \{0, 1\}$
Where the decision variables x[i]
refer to whether or not to use rectangle i
, covers(i, j)
is the set of rectangles that contain the cell (i, j)
, area
is the vector of the areas of the rectangles, and the set of rectangles used is all 2x2, 2x3, 3x2 and 3x3 rectangles that fit on the grid and contain at least one red cell. You can use a slightly smaller set, for example it is never necessary to use a piece that's bigger than 2x2 that covers only 1 red cell, it could always be replaced by a 2x2 piece and give a better solution. Any rectangles of other legal sizes can be constructed from these pieces so they can be left out.
Actually even fewer rectangles can be used. For example, a rectangle that can be replaced by a smaller rectangle without uncovering any red cells is redundant. There is also the case where a 3x3 can be replaced by 2 2x2 rectangles, that potentially overlap, such that they together cover (at least) the same red cells, making the 3x3 redundant.
Experiment shows that presolving removes almost all columns (for relatively sparse problems), suggesting that it should be easy to a-priori not-generate many of them. I have not looked into that too deeply yet.
Despite ILP being NP-hard, large instances such as this or even this were solved in a couple of seconds. Maybe there is also an inherently efficient way though, I'm not sure.
I don't get any reply
- you are expected to give a site's members a fair chance to answer, and "wait" about a week. You can ask moderators to move your question to a different site.) (I design this problem by myself
- the images look taken from a text book.) Take a look at boolean logic implementation using Gray code maps. $\endgroup$