## Abstract

We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e., 1 × 2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2 × 2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2 × 2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and I-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASPcompleteness of the counting and the another- solutionproblem variants, respectively.

Original language | English |
---|---|

Pages | 211-216 |

Number of pages | 6 |

Publication status | Published - 2012 |

Event | 24th Canadian Conference on Computational Geometry, CCCG 2012 - Charlottetown, PE, Canada Duration: 2012 Aug 8 → 2012 Aug 10 |

### Conference

Conference | 24th Canadian Conference on Computational Geometry, CCCG 2012 |
---|---|

Country/Territory | Canada |

City | Charlottetown, PE |

Period | 12/8/8 → 12/8/10 |