In an irregular grid comprised of squares, how might we find the most efficient way to remove squares such that there is no 2x2 square possible?

1.1k Views Asked by At

Normally in a square grid such as a 5x5 grid

fig 1

the way to accomplish this would to be to remove only 4 squares such that no two touch the wall of the grid, nor do they touch one another

fig 2

This has a very similar arrangement even when you reduce the size of the overall grid by 1 row and/or 1 column

fig 3

What I'm trying to figure out is how few squares I could remove from an irregular shape

irregular shape

or one with squares already removed in order to stop any 2x2 square from being possible.