Document Open Access Logo

On the Complexity of Lattice Puzzles

Authors Yasuaki Kobayashi, Koki Suetsugu , Hideki Tsuiki, Ryuhei Uehara

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2019.32.pdf
  • Filesize: 1.45 MB
  • 12 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Lattice puzzle
  • NP-completeness
  • GI-completeness
  • FPT algorithm

Metrics

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

Abstract

In this paper, we investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n x n. It has a long history in the puzzle society; however, there is no known research from the viewpoint of theoretical computer science. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. That is, the variant is GI-complete in general. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes. That is, it gives us new insight of these computational complexity classes.

Cite As Get BibTex

Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara. On the Complexity of Lattice Puzzles. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.32

Author Details

Yasuaki Kobayashi
  • Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501 Japan
Koki Suetsugu
  • National Institute of Informatics, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430 Japan
Hideki Tsuiki
  • Graduate School of Human and Environmental Studies, Kyoto University, Yoshida Nihonmatsu-cho, Sakyo-ku, Kyoto 606-8501 Japan
Ryuhei Uehara
  • School of Information Science, Japan Advanced Institute of Science and Technology, Asahidai, Nomi, Ishikawa 923-1292, Japan

Funding

This work is partially supported by KAKENHI grant numbers 15K00015, 17H06287, and 18H04091, and JST CREST JPMJCR1401.

Acknowledgements

The authors thank Prof. Shuji Yamada for his introduction of his original designed lattice puzzle to the first three authors. The authors also thank JCDCGGG 2017 for giving a chance to give an oral presentation of the early work on this topic, which motivated the last author to join this research. The last author thanks Hisayoshi Akiyama and Mineyuki Uyematsu who kindly taught him the history of the lattice puzzle.

References

  1. Hisayoshi Akiyama. Cube Puzzle Book (in Japanese). Shinkigensha, 2004. Google Scholar
  2. E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathematical Plays, volume 1-4. A K Peters Ltd., 2001-2003. Google Scholar
  3. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  4. M.R. Garey and D.S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, 1979. Google Scholar
  5. R. A. Hearn and E. D. Demaine. Games, Puzzles, and Computation. A K Peters Ltd., 2009. Google Scholar
  6. Takumi Kasai, Akeo Adachi, and Shigeki Iwata. Classes of pebble games and complete problems. SIAM Journal on Computing, 1979. Google Scholar
  7. R. Uehara, S. Toda, and T. Nagoya. Graph Isomorphism Completeness for Chordal Bipartite Graphs and Strongly Chordal Graphs. Discrete Applied Mathematics, 145(3):479-482, 2004. URL: https://doi.org/10.1016/j.dam.2004.06.008.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact