8x8 grid with no unmarked L-pentomino

Question

What is the minimum number of cells on a 8x8 chessboard that need to be marked so that the unmarked cells do not contain an L-pentomino?

An L-pentomino looks like

####
#

or

#
####

Answer 1

I think the answer is

16

cells. One way to achieve it is as follows:

...#...#
..#...#.
.#...#..
#...#...
...#...#
..#...#.
.#...#..
#...#...

There is a straightforward proof that this is the minimum possible.

Consider a rectangular region that is 2 units high and 4 units wide. There are four ways to place an L pentomino. If we are allowed to mark only one out of the 8 cells, there is always one or more ways to place an L pentomino using only unmarked cells.

Since this logic applies everywhere on the grid and the 8x8 grid can be divided into 8 such non-overlapping regions, we need at least 2x8 = 16 marked cells.

Bonus for some other pentominoes:

The same configuration and minimality proof work for Y pentomino.

The same minimality proof works for N and P pentominoes, and the corresponding minimal configuration is

........
.#.#.#.#
........
.#.#.#.#
........
.#.#.#.#
........
.#.#.#.#

Answer 2

import numpy as np
from itertools import product
from z3 import *

l_pentomino = np.array([[1,1,1,1],[1,0,0,0]], dtype=int)
all_l_pentominos = [np.rot90(l_pentomino, i) for i in range(4)]
all_l_pentominos += [np.fliplr(p) for p in all_l_pentominos]

X = np.array(IntVector('x', 8**2), dtype=object).reshape((8,8))
opt = Optimize()
opt.minimize(Sum(X.ravel().tolist()))
opt += [Or(n==0,n==1) for n in X.ravel()]

for i,j,p in product(range(8), range(8), all_l_pentominos):
    if i+p.shape[0]<=8 and j+p.shape[1]<=8:
        opt += Not(And([X[i+di][j+dj]==0 for (di,dj),v in np.ndenumerate(p) if v==1]))

if opt.check() == sat:
    m = opt.model()
    solution = np.array([[m.evaluate(X[i,j]).as_long() for j in range(8)] for i in range(8)])
    print("Minimum number of cells to be marked:", np.sum(solution))
    print(solution)

Minimum number of cells to be marked: 16
[[0 0 0 1 0 0 0 1]
 [1 0 0 0 1 0 0 0]
 [0 1 0 0 0 1 0 0]
 [0 0 1 0 0 0 1 0]
 [0 0 0 1 0 0 0 1]
 [1 0 0 0 1 0 0 0]
 [0 1 0 0 0 1 0 0]
 [0 0 1 0 0 0 1 0]]