3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – user21820
    Commented Apr 19, 2022 at 8:35
  • 1
    $\begingroup$ I guess the next and final question would be: "What is the smallest board area that can contain one of each pentomino type?" $\endgroup$
    – justhalf
    Commented Apr 19, 2022 at 11:53
  • $\begingroup$ @justhalf: Indeed, just ask xd y to get your answer haha.. $\endgroup$
    – user21820
    Commented Apr 19, 2022 at 12:08

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
20
  • $\begingroup$ Thank you! It's a pity I didn't try putting the N-pentamino that way! $\endgroup$
    – user21820
    Commented Apr 19, 2022 at 9:56
  • $\begingroup$ 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. $\endgroup$
    – Oray
    Commented Apr 19, 2022 at 9:57
  • 2
    $\begingroup$ @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. $\endgroup$
    – justhalf
    Commented Apr 19, 2022 at 11:51
  • 1
    $\begingroup$ This question is just a free answer for you, xd y, haha. You just need to change 8x8 to 8x9 and rerun, I guess? $\endgroup$
    – justhalf
    Commented Apr 19, 2022 at 11:52
  • 2
    $\begingroup$ I am now curious what would be the smallest area board that could pack all 12 pentominoes in this manner... $\endgroup$
    – Darrel Hoffman
    Commented Apr 19, 2022 at 21:47

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.