Computational complexity of puzzles and related topics
From MaRDI portal
Publication:6535387
DOI10.4036/IIS.2022.R.06zbMATH Open1541.6816MaRDI QIDQ6535387FDOQ6535387
Authors: Ryuhei Uehara 
Publication date: 15 December 2023
Published in: Interdisciplinary Information Sciences (IIS) (Search for Journal in Brave)
Recommendations
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
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- SOKOBAN and other motion planning problems
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of theorem-proving procedures
- The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
- Alternation
- The complexity of change
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
- Title not available (Why is that?)
- Hard tiling problems with simple tiles
- Hexaflexagons, probability paradoxes, and the Tower of Hanoi. Martin Gardner's first book of mathematical puzzles and games
- The Othello game on an \(n\times n\) board is PSPACE-complete
- Games, puzzles, and computation
- Complexity of independent set reconfigurability problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- On the complexity of reconfiguration problems
- 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
- Title not available (Why is that?)
- The \((n^ 2-1)\)-puzzle and related relocation problems
- Linear-time algorithm for sliding tokens on trees
- Complexity results for standard benchmark domains in planning
- Sliding token on bipartite permutation graphs
- Title not available (Why is that?)
- Introduction to reconfiguration
- Handbook of satisfiability. In 2 parts
- Hashiwokakero is NP-complete
- The Complexity of Solitaire
- Movement Problems for 2-Dimensional Linkages
- A simple proof that the \((n^{2} - 1)\)-puzzle is hard
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Sliding tokens on block graphs
- Sliding tokens on a cactus
- Shikaku and Ripple Effect are NP-complete
- HIROIMONO Is NP-Complete
- Tatamibari is NP-complete
- Shortest reconfiguration sequence for sliding tokens on spiders
- Computational complexity of jumping block puzzles
- NP-completeness of two pencil puzzles: Yajilin and Country Road
- Herugolf and Makaro are NP-complete
- Algorithms for solving Rubik's cubes
- Knots and Borromean rings, rep-tiles, and eight queens.
- Solving the Rubik's Cube Optimally 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
Cited In (2)
This page was built for publication: Computational complexity of puzzles and related topics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535387)
