On the Computational Complexity of Generalized Common Shape Puzzles

Abstract In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S1 and S2 of polyominoes. The first puzzle asks us to form the same shape using polyominoes in S1 and S2. We demonstrate that this is polynomial-time solvable if S1 and S2 have constant numbers of polyominoes, and it is strongly NP-complete in general. The second puzzle allows us to make copies of the pieces in S1 and S2. That is, a polyomino in S1 can be used multiple times to form a shape. This is a generalized version of the classical puzzle known as the common multiple shape puzzle. For two polyominoes P and Q, the common multiple shape is a shape that can be formed by many copies of P and many copies of Q. We show that the second puzzle is undecidable in general. The undecidability is demonstrated by a reduction from a new type of undecidable puzzle based on tiling. Nevertheless, certain concrete instances of the common multiple shape can be solved in practical time. We present a method for determining the common multiple shape for provided tuples of polyominoes and outline concrete results, which improve on the previously known results in the puzzle community.