A solitaire Blokus problem on a rectangular board

Question

Rules

As in Blokus, you have a total of 21 pieces (every piece from monomino to pentomino) in hand:

All of these polyominoes are free, this means that you can rotate or flip them as you wish before placing them on the board.

The only rule is that placed polyominos mustn't touch each other by the edge; however, touchings by the corner are acceptable.

(Unlike in the original game, it isn't an obligation for every piece to be corner to corner with at least one of the existing pieces)

Your goal is to fit all the pieces into a K-row rectangular board (where K is fixed) while trying to minimize the columns used.

How many columns is optimal for K=11? Please give your answer and proof.

An example of 11x15:

The polyominoes cover a total of 89 squares. The total exclusion area is 187, but these squares can overlap. If we assume a minimal exclusion of 93 squares, including a full row and full column for top and left edges, an optimal solution would have $(r+1)(c+1)\ge182$. By this measure, most of your solutions should be optimal. — Daniel Mathias, Commented Aug 15, 2021 at 14:31
Please see The end of open-ended puzzles - asking this as a "beat my best" challenge is a game, not a puzzle, and for the reasons explained in that post are generally off-topic now. I think you really want to ask for how many columns is optimal for a given K (or, perhaps, for any K) with proof of optimality. — Rubio, Commented Aug 15, 2021 at 17:53
Thank you @Rubio for pointing out my problems. I have edited my post to make it more of a puzzle than a game. — sunnyshi, Commented Aug 16, 2021 at 3:11
I have just found out some K=5, 8, 9, 11, 12 results on this site: link — sunnyshi, Commented Aug 16, 2021 at 4:52
@DanielMathias That inequality is violated by some of the upper bounds like $(r,c)=(8,19)$. A valid inequality is instead $4(rc-89)+2r+2c \ge 187$, obtained by appending a row to each side of the $rc$ rectangle. Because the LHS is even, the RHS can be strengthened to $188$. — RobPratt, Commented Aug 17, 2021 at 21:45

RobPratt · Accepted Answer · 2021-08-16 20:45:09Z

1

For $K=4$,

the minimum number of columns is in $[34,37]$ (an improvement by $1$ of your upper bound):

For $K\in\{8,9,11\}$,

the minimum number of columns matches the solutions in the link found by @sunnyshi

For $K=10$,

the minimum number of columns is $16$:

For $K=12$,

the minimum number of columns is $13$:

answered Aug 16, 2021 at 0:58

RobPratt

15.7k1 gold badge35 silver badges61 bronze badges

1

$\begingroup$ Do you have a proof? $\endgroup$
– bobble
Commented Aug 16, 2021 at 1:42
1

$\begingroup$ I used integer linear programming. $\endgroup$
– RobPratt
Commented Aug 16, 2021 at 2:06
$\begingroup$ Thanks @RobPratt. I guess I'll try to figure other scenarios myself... $\endgroup$
– sunnyshi
Commented Aug 18, 2021 at 14:02

Add a comment |