9
$\begingroup$

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.

enter image description here

Can anyone come up with a solution using only 18 or less?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
$\begingroup$

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 .

Improve this answer
$\endgroup$
2
  • $\begingroup$ Beat me to it! (as usual) $\endgroup$
    – Paul Panzer
    Commented Aug 24, 2020 at 11:45
  • 2
    $\begingroup$ That looks like an optimal solution indeed since all groups have 4. Thank you very much! :D $\endgroup$
    – user71119
    Commented Aug 24, 2020 at 11:45
6
$\begingroup$

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}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.