Fitting pentominoes inside a 10x10 grid

Question

What is the most number of pentominoes that you can fit inside a 10x10 grid, such that they do not overlap or touch each other orthogonally (horizontally or vertically)?

Bonus: what is the most number of distinct free pentominoes you can fit?

Answer 1

Bonus:

The maximum number of distinct free pentominoes is $12$:

W.YYYY.UUU
WW.Y...U.U
.WW.NNN.X.
T..NN..XXX
TTT..FF.X.
T..ZZ.FF.I
.PP.Z.F..I
PPP.ZZ.V.I
...L...V.I
LLLL.VVV.I

I used integer linear programming as follows. Introduce binary decision variable $x_p$ for each possible placement of a pentomino in the grid. Let binary decision variable $y_{ij}$ indicate whether cell $(i,j)$ is an orthogonal neighbor of at least one selected pentomino. Let $P_{ij}$ be the set of pentominoes that contain cell $(i,j)$. Let $N_p$ be the set of cells that neighbor pentomino $p$. The original problem is to maximize $\sum_p x_p$ subject to \begin{align} \sum_{p\in P_{ij}} x_p + y_{ij} &\le 1 &&\text{for all $(i,j)$} \tag1\label1 \\ x_p &\le y_{ij} &&\text{for all $p$ and $(i,j)\in N_p$} \tag2\label2 \end{align} Constraint \eqref{1} prevents cell $(i,j)$ from appearing in more than one selected pentomino and from both appearing in one selected pentomino and neighboring a selected pentomino. Constraint \eqref{2} forces $y_{ij}=1$ for all cells $(i,j)$ that neighbor selected pentomino $p$.

For the bonus problem, let $t_p$ be the type (F,I,L,N,P,T,U,V,W,X,Y,Z) of pentomino $p$, and let binary decision variable $z_t$ indicate whether at least one pentomino of type $t$ is selected. The problem is to maximize $\sum_t z_t$ subject to \eqref{1}, \eqref{2}, and \begin{align} z_t &\le \sum_{p: t_p = t} x_p &&\text{for all $t$} \tag3\label3 \end{align} Constraint \eqref{3} forces some pentomino of type $t$ to be selected if $z_t=1$.

Answer 2

As a quick baseline solution:

12 pentominoes

IIIII.NNN.
.....NN..Z
VVV.X..ZZZ
V..XXX.Z..
V.X.X.F.UU
.XXX.FFF.U
L.X..F..UU
L..FF.WW..
L.FF.WW.PP
LL.F.W.PPP

Bonus:

11 distinct pentominoes (Y missing)

IIIII.NNN.
.....NN..Z
VVV.X..ZZZ
V..XXX.Z..
V...X.F.UU
.....FFF.U
L....F..UU
L.TTT.WW..
L..T.WW.PP
LL.T.W.PPP

---

(Edit) I also found a nice symmetric solution for the first question:

12 pentominoes + an L triomino

.YYYY.WW.Y
Y.Y..WW.YY
YY.X.W.F.Y
Y.XXX.FF.Y
Y..X.X.FF.
.WW.XXX..F
WW.F.X.FFF
W.FFF.F.F.
.Y..F.FF.x
YYYY.FF.xx

I wonder what Hexomino's solution is...

Answer 3

Rob Pratt beat me to it, but I'll post anyway because my computer found a couple of other solutions to the bonus question.

I used my own program to solve it. I ran it overnight, and after 15 hours it had only found these two solutions. I'll leave it running, but I don't know how long it takes to do an exhaustive search. By the way, I fixed the orientation of the Y pentomino to filter out rotations/reflections.

Edit:
The search finished after 30+ hours, and the only other solutions it found were Rob's solution and two minor variations of it, making a total of 5 distinct solutions.