Mathematical characterizations and computational complexity of anti-slide puzzles
Ko Minamisawa, Ryuhei Uehara, Masao Hara · Theoretical Computer Science · 2022
For a given set of pieces and a frame, an anti-slide puzzle asks us to arrange the pieces so that none of the pieces can slide in the frame. Since the first anti-slide puzzle that consists of dozens of cuboid pieces in 3D was invented, tons of anti-slide puzzles using pentominoes have been proposed. Some of them are not in a frame, which we call that interlock puzzles. In this paper, we investigate computational complexity of anti-slide puzzles and interlock puzzles in 2D. In previous work in theoretical computer science, a few models have been proposed for dealing with the notion of anti-slide, however, there exist gaps between these models and real puzzles. We first give mathematical characterizations of anti-slide puzzles and show the relationship between the previous work. Using a mathematical characterization, we give a polynomial time algorithm for determining if a given arrangement of polyominoes is anti-slide or not in a model. Next, we prove that the decision problem whether a given set of polyominoes can be arranged to be anti-slide or not is strongly NP-complete even if every piece is x-monotone. On the other hand, a set of pieces cannot be arranged to be interlocked if all pieces are convex polygons.