Document Open Access Logo

Gourds: A Sliding-Block Puzzle with Turning

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.33.pdf
  • Filesize: 1.94 MB
  • 16 pages

Document Identifiers

Author Details

Joep Hamersma
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Marc van Kreveld
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Yushi Uno
  • Graduate School of Engineering, Osaka Prefecture University, Japan
Tom C. van der Zanden
  • Department of Data Analytics and Digitalisation, Maastricht University, The Netherlands

Funding

  • van Kreveld, Marc: Partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651.
  • Uno, Yushi: Partially supported by JSPS KAKENHI Grant Number JP17K00017 and by JST CREST Grant Number JPMJCR1402, Japan.

Acknowledgements

The original idea for Gourds was formed after an invited talk by Ryuhei Uehara at ICALP 2015.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ISAAC.2020.33

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • computational complexity
  • divide-and-conquer
  • Hamiltonian cycle
  • puzzle game
  • (combinatorial) reconfiguration
  • sliding-block puzzle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 × 1 Rush Hour with fixed blocks is PSPACE-complete. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.09914.
  2. Kevin Buchin and Maike Buchin. Rolling block mazes are PSPACE-complete. Information and Media Technologies, 7(3):1025-1028, 2012. Google Scholar
  3. Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-Khechen, Sándor P. Fekete, Christian Knauer, André Schulz, and Perouz Taslakian. On rolling cube puzzles. In CCCG, pages 141-144, 2007. Google Scholar
  4. Erik D. Demaine and Mikhail Rudoy. A simple proof that the (n²-1)-puzzle is hard. Theor. Comput. Sci., 732:80-84, 2018. URL: https://doi.org/10.1016/j.tcs.2018.04.031.
  5. Gary William Flake and Eric B. Baum. Rush Hour is PSPACE-complete, or "why you should generously tip parking lot attendants". Theor. Comput. Sci., 270(1-2):895-911, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00173-6.
  6. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci., 343(1-2):72-96, 2005. Google Scholar
  7. Robert A. Hearn and Erik D. Demaine. Games, Puzzles and Computation. A K Peters, 2009. Google Scholar
  8. Wm. Woolsey Johnson and William E. Story. Notes on the "15" puzzle. American Journal of Mathematics, 2(4):397-404, 1879. URL: http://www.jstor.org/stable/2369492.
  9. Graham Kendall, Andrew Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13-34, 2008. Google Scholar
  10. Christos Nomikos, Aris Pagourtzis, and Stathis Zachos. Randomized and approximation algorithms for blue-red matching. In International Symposium on Mathematical Foundations of Computer Science, pages 715-725. Springer, 2007. Google Scholar
  11. Valentin Polishchuk, Esther M. Arkin, and Joseph S. B. Mitchell. Hamiltonian cycles in triangular grids. In Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, 2006. URL: http://www.cs.queensu.ca/cccg/papers/cccg17.pdf.
  12. Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, and Andreas Wotzlaw. XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics, 167:1-14, 2014. URL: https://doi.org/10.1016/j.dam.2013.10.030.
  13. Daniel Ratner and Manfred K. Warmuth. Finding a shortest solution for the N× N extension of the 15-puzzle is intractable. In AAAI, pages 168-172. Morgan Kaufmann, 1986. Google Scholar
  14. Jerry Slocum and Dic Sonneveld. The 15 Puzzle. Slocum Puzzle Foundation, 2nd edition, 2005. Google Scholar
  15. Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. The International Journal of Robotics Research, 35(14):1750-1759, 2016. Google Scholar
  16. Georgios Stamoulis. Approximation algorithms for bounded color matchings via convex decompositions. In International Symposium on Mathematical Foundations of Computer Science, pages 625-636. Springer, 2014. Google Scholar
  17. John Tromp and Rudi Cilibrasi. Limits of Rush Hour logic complexity. CoRR, abs/cs/0502068, 2005. URL: http://arxiv.org/abs/cs/0502068.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact