Computational complexity of puzzles and related topics

DOI10.4036/iis.2022.r.06zbMath1541.6816MaRDI QIDQ6535387

Ryuhei Uehara

Publication date: 15 December 2023

Published in: Interdisciplinary Information Sciences (IIS) (Search for Journal in Brave)

zbMATH Keywords

puzzlegamecomputation modelcombinatorial reconfigurationcomputational complexity class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Applications of game theory (91A80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorial games (91A46)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• A new polynomial-time algorithm for linear programming
• Complexity results for standard benchmark domains in planning
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Hashiwokakero is NP-complete
• On alternation
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Othello game on an \(n\times n\) board is PSPACE-complete
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• SOKOBAN and other motion planning problems
• Shortest reconfiguration sequence for sliding tokens on spiders
• Introduction to reconfiguration
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Computational complexity of jumping block puzzles
• The complexity of change
• Sliding Tokens on Block Graphs
• Algorithms for Solving Rubik’s Cubes
• Solving the Rubik's Cube Optimally is NP-complete
• Sliding Token on Bipartite Permutation Graphs
• The Complexity of Solitaire
• Movement Problems for 2-Dimensional Linkages
• Alternation
• Sliding Tokens on a Cactus
• Reducibility among Combinatorial Problems
• HIROIMONO Is NP-Complete
• The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake
• On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game
• The complexity of theorem-proving procedures
• On Computable Numbers, with an Application to the Entscheidungsproblem
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Hard tiling problems with simple tiles
• Tatamibari is NP-complete

This page was built for publication: Computational complexity of puzzles and related topics