Moins de symboles marqués

Question

J'ai une grille 7x7, où je veux trouver le moins de "positions marquées" donc un groupe de positions non marquées n'est pas plus grand que 4 (se déplaçant uniquement vers le haut, le bas, la gauche et la droite et non en diagonale). Voici un exemple avec une solution utilisant 19 symboles marqués.

Quelqu'un peut-il trouver une solution en utilisant seulement 18 ou moins?

Answer 1

Je m'attends à ce que ce soit une solution optimale, mais je n'en ai pas encore la preuve.

Il n'a que 17 carrés marqués.

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

Answer 2

Vous pouvez résoudre ce problème de couverture d'ensemble via la programmation linéaire entière comme suit. Pour chaque pentomino$p$, laisser $C_p$être l'ensemble des (cinq) cellules de la grille qui le composent. Pour chaque cellule de la grille$(i,j)$, laissez la variable de décision binaire $x_{i,j}$indiquer si cette cellule est marquée. Le problème est de minimiser$\sum_{i,j} x_{i,j}$ soumis à des contraintes linéaires: $$\sum_{(i,j)\in C_p} x_{i,j} \ge 1 \quad \text{for all $p$}$$ Les valeurs optimales pour $n\in\{1,\dots,10\}$sont \ 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 {matrice}