Computational complexity of jumping block puzzles

DOI10.1007/978-3-030-89543-3_54MaRDI QIDQ2695336zbMATH OpenOpenAlexFDO

Authors Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara

Publication date 30 March 2023

Full work available at URL https://arxiv.org/abs/2109.02213

zbMATH Keywords

combinatorial reconfigurationcomputational complexityjumping block puzzlesliding block puzzletoken jumping

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

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

Cited in

(2)

• The computational complexity of Angry Birds
• Computational complexity of puzzles and related topics

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 Q2695336)