1 Search Results for "Hamersma, Joep"


Document
Gourds: A Sliding-Block Puzzle with Turning

Authors: Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)


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.

Cite as

Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden. Gourds: A Sliding-Block Puzzle with Turning. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{hamersma_et_al:LIPIcs.ISAAC.2020.33,
  author =	{Hamersma, Joep and van Kreveld, Marc and Uno, Yushi and van der Zanden, Tom C.},
  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 =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.33},
  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}
}
  • Refine by Author
  • 1 Hamersma, Joep
  • 1 Uno, Yushi
  • 1 van Kreveld, Marc
  • 1 van der Zanden, Tom C.

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 (combinatorial) reconfiguration
  • 1 Hamiltonian cycle
  • 1 computational complexity
  • 1 divide-and-conquer
  • 1 puzzle game
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail