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
#
####
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
#
####
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
........ .#.#.#.# ........ .#.#.#.# ........ .#.#.#.# ........ .#.#.#.#
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]]