# A solitaire Blokus problem on a rectangular board

## 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)

## Goal

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.

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. 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
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. Aug 16, 2021 at 3:11
• I have just found out some K=5, 8, 9, 11, 12 results on this site: link 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$. Aug 17, 2021 at 21:45

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$$: • Do you have a proof? Aug 16, 2021 at 1:42
• I used integer linear programming. Aug 16, 2021 at 2:06
• Thanks @RobPratt. I guess I'll try to figure other scenarios myself... Aug 18, 2021 at 14:02