# 8x8 grid with no unmarked L-pentomino

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

#
####

• Is it allowed to rotate the L-pentominos? Commented Jul 8 at 9:19
• You can rotate and reflect them. Commented Jul 8 at 9:22
• Shouldn’t this question be “so that only the unmarked cells contain an L-pentomino”? Commented Jul 8 at 12:03
• @JudahOfChelm No, that's a different puzzle, and one with a trivial solution (mark no cells at all). Commented Jul 9 at 2:50
• Ah, got it. I was misreading the grid in the solution. Thanks. Commented Jul 9 at 9:06

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

• Nice! I found the minimum solution for the other pentominoes as well. Commented Jul 8 at 8:30