5
$\begingroup$

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

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

2 Answers 2

16
$\begingroup$

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

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

$\endgroup$
6
$\begingroup$
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]]

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.