License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.33
URN: urn:nbn:de:0030-drops-133773
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13377/
Go to the corresponding LIPIcs Volume Portal

Hamersma, Joep ; van Kreveld, Marc ; Uno, Yushi ; van der Zanden, Tom C.

Gourds: A Sliding-Block Puzzle with Turning

pdf-format:
LIPIcs-ISAAC-2020-33.pdf (2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{hamersma_et_al:LIPIcs:2020:13377,
  author =	{Joep Hamersma and Marc van Kreveld and Yushi Uno and Tom C. van der Zanden},
  title =	{{Gourds: A Sliding-Block Puzzle with Turning}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13377},
  URN =		{urn:nbn:de:0030-drops-133773},
  doi =		{10.4230/LIPIcs.ISAAC.2020.33},
  annote =	{Keywords: computational complexity, divide-and-conquer, Hamiltonian cycle, puzzle game, (combinatorial) reconfiguration, sliding-block puzzle}
}

Keywords: computational complexity, divide-and-conquer, Hamiltonian cycle, puzzle game, (combinatorial) reconfiguration, sliding-block puzzle
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI