8
$\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?

$\endgroup$
6
$\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$
  • $\begingroup$ Beat me to it! (as usual) $\endgroup$ – Paul Panzer Aug 24 at 11:45
  • 1
    $\begingroup$ That looks like an optimal solution indeed since all groups have 4. Thank you very much! :D $\endgroup$ – user71119 Aug 24 at 11:45
7
$\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, privacy policy and cookie policy

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