2026-07-24T06:45:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13377 2024-03-06T10:51:49Z ddc:004 open_access

Gourds: A Sliding-Block Puzzle with Turning Hamersma, Joep van Kreveld, Marc Uno, Yushi van der Zanden, Tom C. computational complexity divide-and-conquer Hamiltonian cycle puzzle game (combinatorial) reconfiguration sliding-block puzzle We propose a new kind of sliding-block puzzle, called Gourds, where the objective is to rearrange 1×2 pieces on a hexagonal grid board of 2n+1 cells with n pieces, using sliding, turning and pivoting moves. This puzzle has a single empty cell on a board and forms a natural extension of the 15-puzzle to include rotational moves. We analyze the puzzle and completely characterize the cases when the puzzle can always be solved. We also study the complexity of determining whether a given set of colored pieces can be placed on a colored hexagonal grid board with matching colors. We show this problem is NP-complete for arbitrarily many colors, but solvable in randomized polynomial time if the number of colors is a fixed constant. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joep Hamersma and Marc van Kreveld and Yushi Uno and Tom C. van der Zanden 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.33 urn:nbn:de:0030-drops-133773 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.33 eng https://creativecommons.org/licenses/by/3.0/legalcode