Puzzles are Hard Enough Just by Rotations

In this paper, we investigate the computational complexity of a series of puzzles. We are given a set of n centers of circles and n unit disks. Each disk is based on a unit circular shape, but a part of it can be bitten by other disks, which is called a lune. We investigate three variants of this puzzle. First, we investigate the classic packing puzzle of disks and lunes. We note that the centers of disks are given as a part of input, and some disks can be lunes. Therefore, essentially, we can only choose and rotate the lunes to pack them. (In our reduction, the assignment of lunes is easy to find. Therefore, only rotations of them are crucial.) Even under this strong constraint, the packing problem is still NP-complete. Next we turn to the combinatorial reconfiguration variant of this puzzle. That is, we are given two nonoverlapping arrangements of disks and lunes on a given set of centers on a board. Each disk is pinned at the center, and thus we can just rotate it. The problem asks if we can transform one to the other by just rotations of disks and lunes without overlapping. We show that this puzzle is PSPACE-complete in general. Lastly, we focus on the cases in which the puzzle can be solved in polynomial time. The first tractable case is a one-dimensional packing puzzle. The second one is the screw-type variant of this puzzle. In this variant, each disk or lune is realized by a thick screw. We are given a nonoverlapping arrangement of them. The operation we can do is that we can screw a disk or lune if its orbit is not blocked by any other disk or lune. We prove that this variant can be solved in polynomial time.