# Fitting pentominoes inside a 10x10 grid

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?

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$$.

• That is awesome! Well done. I had a feeling that the bonus is possible, but couldn't find it. Can you share your method? Commented Jun 14, 2022 at 23:36
• Best use of Operations Research I've seen.
– iBug
Commented Jun 15, 2022 at 8:55

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

• That's a great start! Commented Jun 14, 2022 at 11:10
• @DmitryKamenetsky Do you have a solution which outdoes this? I can get really close rot13(gjryir cragbzvabrf naq bar grgebzvab) but can't outdo it, yet. Commented Jun 14, 2022 at 15:13
• I cannot outdo this, but my gut feeling is that the bonus can be improved... Commented Jun 14, 2022 at 15:20
• Your first solution is optimal. Commented Jun 14, 2022 at 22:45
• I may ask it as another question Commented Jun 15, 2022 at 9:32

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.

• Now after searching 19 hours it also found Rob's solution, plus a variation where the V and I pentominoes are flipped around. Commented Jun 15, 2022 at 11:03
• Cool. Thx for the link. Let us know how long it takes to finish and how many were found.
– JLee
Commented Jun 15, 2022 at 12:30
• Now there is a fifth solution - a variant of Rob's solution where you first flip I and V around, and then flip I and L. Commented Jun 15, 2022 at 12:45
• @JLee Those 5 solutions are all of them - the two above, and Rob's solution and two minor variants of it. I forgot to note the time the search took, but it must have been thirty-something hours. My program is not very fast, but it makes up for it in versatility. Commented Jun 16, 2022 at 7:28
• The right solution in the first spoiler and the rightmost solution in the second spoiler are closely related - they only differ in whether the L and I pieces are placed on top or on bottom. Commented Jan 12, 2023 at 21:19