On the Computational Complexity of Generalized Common Shape Puzzles

In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets \(\mathcal{S}_1\) and \(\mathcal{S}_2\) of polyominoes. The first puzzle asks us to form the same shape using polyominoes in \(\mathcal{S}_1\) and \(\mathcal{S}_2\) . We demonstrate that this is polynomial-time solvable if \(\mathcal{S}_1\) and \(\mathcal{S}_2\) 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 \(\mathcal{S}_1\) and \(\mathcal{S}_2\) . That is, a polyomino in \(\mathcal{S}_1\) 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 a 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.