マークされたシンボルの最小数

Question

私は7x7グリッドを持っています。ここでは、「マークされた位置」の量を最小限に抑えて、マークされていない位置のグループが4より大きくならないようにします（上下左右に移動するだけで、対角線ではありません）。以下は、19個のマークされたシンボルを使用するソリューションの例です。

誰もが18以下を使用して解決策を思い付くことができますか？

Answer 1

これが最適な解決策になると思いますが、その証拠はまだありません。

マークされた正方形は17個だけです。

。バツ 。。。バツ 。
 。。バツ 。バツ 。。
 。バツ 。バツ 。バツ 。
 バツ 。。バツ 。。バツ
 。バツ 。バツ 。バツ 。
 。。バツ 。バツ 。。
 。バツ 。。。バツ 。

Answer 2

この集合被覆問題は、次のように整数線形計画法を介して解決できます。ペントミノごとに$p$、 $C_p$それを構成する（5つの）グリッドセルのセットである。グリッドセルごと$(i,j)$、バイナリ決定変数を許可します $x_{i,j}$そのセルがマークされているかどうかを示します。問題は最小化することです$\sum_{i,j} x_{i,j}$ 線形制約の対象： $$\sum_{(i,j)\in C_p} x_{i,j} \ge 1 \quad \text{for all $p$}$$ の最適値 $n\in\{1,\dots,10\}$されている\ {行列}始めるN＆1＆2＆3＆4＆5＆6＆7＆8＆9＆10 \\ \ HLINE \分＆0 0 3・5・8・13・17・24・31＆39 \\ \ end {matrix}