11
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

8
$\begingroup$

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

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

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

$\endgroup$
5
  • $\begingroup$ That's a great start! $\endgroup$ Jun 14, 2022 at 11:10
  • $\begingroup$ @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. $\endgroup$
    – hexomino
    Jun 14, 2022 at 15:13
  • $\begingroup$ I cannot outdo this, but my gut feeling is that the bonus can be improved... $\endgroup$ Jun 14, 2022 at 15:20
  • 2
    $\begingroup$ Your first solution is optimal. $\endgroup$
    – RobPratt
    Jun 14, 2022 at 22:45
  • $\begingroup$ I may ask it as another question $\endgroup$
    – hexomino
    Jun 15, 2022 at 9:32
5
$\begingroup$

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

enter image description here

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.

enter image description here

$\endgroup$
6
  • 1
    $\begingroup$ Now after searching 19 hours it also found Rob's solution, plus a variation where the V and I pentominoes are flipped around. $\endgroup$ Jun 15, 2022 at 11:03
  • $\begingroup$ Cool. Thx for the link. Let us know how long it takes to finish and how many were found. $\endgroup$
    – JLee
    Jun 15, 2022 at 12:30
  • $\begingroup$ 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. $\endgroup$ Jun 15, 2022 at 12:45
  • 2
    $\begingroup$ @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. $\endgroup$ Jun 16, 2022 at 7:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – isaacg
    Jan 12, 2023 at 21:19

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.