Polyomino Packing

Given a collection of polyominoes, pack them into a target shape.

Description

Given a collection of (not necessarily distinct) polyominoes and a target shape $S$, which is also a polyomino, the goal is to find a packing of the polyominoes into $S$, i.e., to place each polyomino inside the target shape so that no two polyominoes intersect. Notice that the area of $S$ might be larger than the sum of the areas of the polyominoes.

Depending on the version of the problem, horizontal or vertical reflection and rotations multiples of 90 degrees of the polyominoes might be allowed.

The picture shows $1$ tetromino abd $12$ pentominoes packed in a $8 \times 8$ square.

Computational complexity

The above results also hold when rotations and/or reflections are allowed.

References

[1] E. D. Demaine, M. L. Demaine. Jigsaw Puzzles, “Edge Matching, and Polyomino Packing: Connections and Complexity”, Graphs and Combinatorics, 2007.

[2] M. Brand, “Small polyomino packing”, Information Processing Letters, 2017.

[3] H. L. Bodlaender, T. C. van der Zanden, “On the Exact Complexity of Polyomino Packing”, in FUN 2018

Picture by Jeffrey Bary (CC BY 2.0).