# Least number of marked symbols

I have a 7x7 grid, where I want to find the least amount of "marked positions" so a group of non-marked positions aren't bigger then 4 (only moving up, down, left and right and not diagonal). Below is an example with a solution of using 19 marked symbols. Can anyone come up with a solution using only 18 or less?

I expect this to be an optimal solution, but have no proof of that yet.

It has just 17 marked squares.

 . X . . . X .
. . X . X . .
. X . X . X .
X . . X . . X
. X . X . X .
. . X . X . .
. X . . . X .

• Beat me to it! (as usual) – Paul Panzer Aug 24 at 11:45
• That looks like an optimal solution indeed since all groups have 4. Thank you very much! :D – user71119 Aug 24 at 11:45

You can solve this set covering problem via integer linear programming as follows. For each pentomino $$p$$, let $$C_p$$ be the set of (five) grid cells that comprise it. For each grid cell $$(i,j)$$, let binary decision variable $$x_{i,j}$$ indicate whether that cell is marked. The problem is to minimize $$\sum_{i,j} x_{i,j}$$ subject to linear constraints: $$\sum_{(i,j)\in C_p} x_{i,j} \ge 1 \quad \text{for all p}$$ The optimal values for $$n\in\{1,\dots,10\}$$ are $$\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \min & 0 & 0 & 3 & 5 & 8 & 13 & 17 & 24 & 31 & 39 \\ \end{matrix}$$