Matrix covering by squares
This was proved NP-complete in &quot;Optimal Packing and Covering in the Plane are NP-complete&quot; (Fowler, Paterson and Tanimoto, Information Processing Letters 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I recommend reading it!
For each variable they construct a &quot;loop of wire&quot; having an even number of points (1-cells in your formulation), and such that a single square can cover two adjacent points in the loop but no more. This means that there are two ways to cover all points in the loop using a minimal number of squares: Either use a square to cover points 1 and 2, another square to cover points 3 and 4, and so on, or use a square to cover points 2 and 3, another square to a cover points 4 and 5, and so on. Which minimal cover is used corresponds to whether the variable is assigned a value of true or false.
For each clause, they add a single extra point out to the right, and &quot;extrude&quot; the wire loops for the three relevant literals near this point. If any of them is in the right state, the extra point for this clause can be covered &quot;for free&quot; by a square in that loop. Negated literals are achieved simply by slightly compressing a few links in the loop, so that at a position to the right of the compression zone the &quot;parity&quot; of the wire is reversed.
In order to thread the loops through each clause they participate in, wires need to be able to cross over with their signals remaining independent. Interestingly, this &quot;just works&quot; without any additional gadgets.