Timeline for How many distinct pentominos can be placed on a 8×9 board?
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20, 2022 at 15:21 | comment | added | justhalf | Yes, you asked for Blokus in the comment above. I was wondering for the pentomino set, which is a natural extension of this question. | |
| Apr 20, 2022 at 12:05 | comment | added | user21820 | @justhalf: Actually it was for precisely the block set I wanted (in my above comment). In particular, it claims that 10×15 is impossible, answering my question (assuming Rob Pratt's solver has no bug). =) | |
| Apr 20, 2022 at 10:58 | comment | added | justhalf | @user21820 nice find. That's for different block set though. But yeah, it's quite similar. Probably since it's already last year you can still ask that question specifically for pentomino if you want :) | |
| Apr 20, 2022 at 10:32 | comment | added | user21820 | @xdy: I'm surprised that your solver is slow for 11×9. I'm very sure that any solver based on the heuristics I had mentioned in my earlier post would instantly (i.e. <1 s) either find a solution or prove that it is impossible, for such packing puzzles even up to the size 11×14 that I was interested in. I don't have time now to code, but let me know if you would like me to explain the approach (we can continue in chat). | |
| Apr 20, 2022 at 10:22 | comment | added | user21820 | @justhalf: No need; I found this post by (guess who?) Rob Pratt with all the board widths. =) | |
| Apr 20, 2022 at 10:17 | comment | added | justhalf | @user21820 at this point I think it might be getting too close to a non-interesting puzzle series (a series of puzzles which are very similar, just a slightly changed requirements). So I guess maybe one more question that is generic enough as the final question might work. But doing another "fit as many pieces as possible into this board" might be too repetitive. That's why I suggest asking, as the final question, "what is the minimum board size to fit these pieces" or something like that. | |
| Apr 20, 2022 at 2:47 | comment | added | xd y | @DarrelHoffman 10x10 yes, 10x9 no. 11x9 really slow, not sure if possible. | |
| Apr 19, 2022 at 21:47 | comment | added | Darrel Hoffman | I am now curious what would be the smallest area board that could pack all 12 pentominoes in this manner... | |
| Apr 19, 2022 at 18:16 | comment | added | user21820 | That's right; the formulation and also heuristics are important in getting good performance. By the way, since you already have this solver... Many years ago, I tried to pack all the Blokus pieces (i.e. all ≤5-ominos) into a 11×14 board. If I recall correctly, I failed at that time. But just now I succeeded (by hand)! I believe 10×15 is impossible (it needs something like 10 gaps and 5 untouched corners inside the board and no empty 2×2 square). How fast does your solver handle this board size? And should I post the 11×14 challenge as no-computers? | |
| Apr 19, 2022 at 12:25 | comment | added | xd y | @justhalf Yeah, just I'm so unprofessional that I hard-coded 8x8... have to carefully ctrl-H a little bit... | |
| Apr 19, 2022 at 12:23 | comment | added | xd y | @user21820 I don't think most people write B&B solvers themselves. The main effort is to come up with a formulation with good performance, sometimes I find it not easy. So that is another type of puzzle for me. And that is why I follow RobPratt here. | |
| Apr 19, 2022 at 12:06 | comment | added | user21820 | @justhalf: Thanks! That every solution has an L or V was unexpected haha.. By the way, I know integer programming and branch-and-bound, and have coded such solvers myself in the past, but I was too lazy to do it myself. After all, you already wrote one for this problem, so no point for me to recode the wheel. =) | |
| Apr 19, 2022 at 11:52 | comment | added | justhalf | 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:51 | comment | added | justhalf | @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 10:21 | comment | added | xd y | @user21820 updated. | |
| Apr 19, 2022 at 10:20 | history | edited | xd y | CC BY-SA 4.0 |
added 79 characters in body
|
| Apr 19, 2022 at 10:09 | comment | added | user21820 | Only 5 solutions (up to symmetry)? If so, you might as well list them all in your answer. =) | |
| Apr 19, 2022 at 10:07 | comment | added | xd y | @user21820 There are four more solutions :) | |
| Apr 19, 2022 at 10:07 | comment | added | xd y | @Oray Please refer to my answer in the 8x8 question. | |
| Apr 19, 2022 at 9:57 | comment | added | Oray | 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. | |
| Apr 19, 2022 at 9:56 | vote | accept | user21820 | ||
| Apr 19, 2022 at 9:56 | comment | added | user21820 | Thank you! It's a pity I didn't try putting the N-pentamino that way! | |
| Apr 19, 2022 at 9:10 | history | answered | xd y | CC BY-SA 4.0 |
