Grid graphs with diagonal edges and the complexity of Xmas mazes
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
Abstract
We investigate the computational complexity of some maze problems, namely the reachability problem for (undirected) grid graphs with diagonal edges, and the solvability of Xmas tree mazes. Simply speaking, in the latter game one has to move sticks of a certain length through a maze, ending in a particular game situation. It turns out that when the number of sticks is bounded by some constant, these problems are closely related to the grid graph problems with diagonals. If on the other hand an unbounded number of sticks is allowed, then the problem of solving such a maze becomes PSPACE-complete. Hardness is shown via a reduction from the nondeterministic constraint logic (NCL) of Demaine and Hearn to Xmas tree mazes.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 1201 / 2012