# 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). 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?" Apr 19, 2022 at 11:53
• @justhalf: Indeed, just ask xd y to get your answer haha.. 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! 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
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. 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? 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... Apr 19, 2022 at 21:47