2
$\begingroup$

Rules

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

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.

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

An example of 11x15:

11x15

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 15, 2021 at 14:31
  • 4
    $\begingroup$ 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. $\endgroup$
    – Rubio
    Aug 15, 2021 at 17:53
  • $\begingroup$ Thank you @Rubio for pointing out my problems. I have edited my post to make it more of a puzzle than a game. $\endgroup$
    – sunnyshi
    Aug 16, 2021 at 3:11
  • $\begingroup$ I have just found out some K=5, 8, 9, 11, 12 results on this site: link $\endgroup$
    – sunnyshi
    Aug 16, 2021 at 4:52
  • $\begingroup$ @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$. $\endgroup$
    – RobPratt
    Aug 17, 2021 at 21:45

1 Answer 1

1
$\begingroup$

For $K=4$,

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

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$: enter image description here

For $K=12$,

the minimum number of columns is $13$: enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ Do you have a proof? $\endgroup$
    – bobble
    Aug 16, 2021 at 1:42
  • 1
    $\begingroup$ I used integer linear programming. $\endgroup$
    – RobPratt
    Aug 16, 2021 at 2:06
  • $\begingroup$ Thanks @RobPratt. I guess I'll try to figure other scenarios myself... $\endgroup$
    – sunnyshi
    Aug 18, 2021 at 14:02

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.