Computational complexity of jumping block puzzles

DOI10.1016/J.TCS.2023.114292MaRDI QIDQ6144017zbMATH OpenOpenAlexFDO

Authors Masaaki Kanzaki, Yota Otachi, G. Viglietta, Ryuhei Uehara

Publication date 5 January 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114292

zbMATH Keywords

combinatorial reconfigurationcomputational complexityjumping block puzzlesliding block puzzletoken jumping

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• An exact algorithm for the Boolean connectivity problem for k-CNF
• Complexity of independent set reconfigurability problems
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Games, puzzles, and computation
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 687006 (Why is no real title available?)
• On the complexity of reconfiguration problems
• On the diameter of reconfiguration graphs for vertex colourings
• Parameterized complexity of graph constraint logic
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Shortest paths between shortest paths
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two

This page was built for publication: Computational complexity of jumping block puzzles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6144017)