# How many distinct pentominos can be placed on a 8×9 board?

Upon proving optimality of an 8-pentomino solution for an 8×8 board, I was curious to see whether there is a 9-pentomino solution for an 8×9 board, namely a way to arrange 9 distinct pentominos within the 8×9 board with no two pentominos sharing an edge. The same counting technique shows that a 10-pentomino solution is impossible. However, I was unable to find a 9-pentomino solution without repeating pentominos. I think it may be possible because I found many semi-solutions with different repeated pentominos:

x x   x   x x x x | x x   x x   x x   | x x x   x x   x x | x x x   x x x   x
x   x x x     x   | x   x x   x x   x | x   x   x   x x x | x   x   x x   x x
x x   x   x     x | x x   x   x   x x |   x   x x         |   x   x     x x
x   x x x   x |     x   x   x x   | x x x     x x x x | x x   x x x     x
x x x     x   x x | x x x   x x     x | x     x x     x   | x     x     x x x
x   x   x   x | x     x x   x x x |   x x   x x x   x | x   x   x   x
x x   x x   x x   |   x x     x     x | x x   x       x x |   x x   x x   x x
x x x   x x   x x | x x x   x x x x   | x   x x x x   x x | x x   x x   x x x


Each does not use any pentomino more than twice. The first has only repeated X,Y-pentominos. The second has only repeated F,W-pentominos. The third has only repeated P,Y-pentominos. The fourth has only repeated P,W-pentominos. These also show that pure counting arguments cannot rule out a solution, because the first semi-solution does not have any N,Z-pentominos but the fourth does, so perhaps there is a real solution using C,F,N,P,T,W,X,Y,Z-pentominos?

Can anyone find a solution or prove that there is none?

• Oh I just found a semi-solution with two L-pentaminos and no other repeated pentamino. Though theoretically, L is worse than all of C,F,N,P,T,W,X,Y,Z in terms of expanded area (see linked post), so I think fewer solutions would use L (if there are any at all). Commented Apr 19, 2022 at 8:35
• I guess the next and final question would be: "What is the smallest board area that can contain one of each pentomino type?" Commented Apr 19, 2022 at 11:53
• @justhalf: Indeed, just ask xd y to get your answer haha.. Commented Apr 19, 2022 at 12:08

My MIP solver said

Yes. 9.

And the length of the following block becomes a spoiler

$$\begin{array}{ccccccccc} &1&1&1& &A& &5&5\\1&1& & &A&A&A& &5\\ & &8&8& &A& &5&5\\2&2& &8&8& &4& & \\2&2& &8& &4&4& &3\\2& &B& &9& &4& &3\\ &B&B& &9& &4& &3\\B&B& &9&9&9& &3&3\end{array}$$

I put all solutions here to keep it tight.

• Thank you! It's a pity I didn't try putting the N-pentamino that way! Commented Apr 19, 2022 at 9:56
• would really like to learn this mip, could you share some documents for it? and how to implement it with it, for example for this question.
– Oray
Commented Apr 19, 2022 at 9:57
• @Oray if you're interested in integer programming, do look for answers from RobPratt as well. He answered lots of Puzzling questions always with integer programming. Commented Apr 19, 2022 at 11:51
• This question is just a free answer for you, xd y, haha. You just need to change 8x8 to 8x9 and rerun, I guess? Commented Apr 19, 2022 at 11:52
• I am now curious what would be the smallest area board that could pack all 12 pentominoes in this manner... Commented Apr 19, 2022 at 21:47