Computational complexity of jumping block puzzles

DOI10.1016/j.tcs.2023.114292OpenAlexW4388573145MaRDI QIDQ6144017

Ryuhei Uehara, Giovanni Viglietta, Yota Otachi, Masaaki Kanzaki

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

computational complexitycombinatorial reconfigurationsliding block puzzlejumping block puzzletoken jumping

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Shortest paths between shortest paths
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• 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
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Finding paths between 3-colorings
• Parameterized Complexity of Graph Constraint Logic
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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