Nagoya University Polyomino World

The Common Multiple Shape Puzzle (CMSP) is defined as the task of finding, for given finite sets S₁, S₂, …, S_n of polyominoes, a common shape that can be tiled separately by each S_i. Multiple copies of the polyominoes from each set may be used. The figure above shows an example solution of a CMSP with S₁ is the set of pentominoes and S₂ is the set of tetrominoes.

CMSP can be considered a generalization of the Polypolyominoes puzzle in which each set has a single polyomino. The figure below shows an example solution of a polypolyominoes with S₁={X-pentomino}, S₂={L-pentomino}, and S₃={N-tetromino}. Polypolyominoes and its variants have been studied by Livio Zucca, Jorge Mireles, Giovanni Resta, and George Sicherman.

All of the solutions listed in our catalog were obtained using ASP encodings we developed.

• Common Multiple Shape Puzzle (in which each set has multiple polyominoes)
• Tetromino-Pentomino (traditional Polypolyominoes)
• Pento-Pento-Tetrominoes (traditional Polypolyominoes)

1. "On the Computational Complexity of Generalized Common Shape Puzzles"
   Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono, and Ryuhei Uehara
   Proceedings of the Forty-ninth International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'24), LNCS 14519, pp. 55-68. Springer (2024)
2. "Polyomino", Wikipedia
3. "Computer Puzzle Solution", DeepGreen (in Japanese)
4. "Poly²ominoes", Jorge Mireles
5. "Polypolyominoes", Giovanni Resta
6. "Polyform Curiosities", Col. George Sicherman

Mutsunori Banbara
Professor
Graduate School of Informatics, Nagoya University
Furo-cho, Chikusa-ward, Nagoya-city, 464-8601