On the complexity of rolling block and Alice mazes
Holzer, Markus ;
Jakobi, Sebastian
Zum Volltext im pdf-Format:
Dokument 1.pdf (422 KB)
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-90846
URL: http://geb.uni-giessen.de/geb/volltexte/2012/9084/
Freie Schlagwörter (Englisch):
constraint logic , puzzles , rolling block maze , Alice maze
Universität
Justus-Liebig-Universität Gießen
Institut:
Institut für Informatik
Fachgebiet:
Informatik
DDC-Sachgruppe:
Informatik
Dokumentart:
ResearchPaper
Zeitschrift, Serie:
IFIG Research Report
; 1202 / 2012
Sprache:
Englisch
Erstellungsjahr:
2012
Publikationsdatum:
23.11.2012
Kurzfassung auf Englisch:
We investigate the computational complexity of two maze problems, namely rolling block and Alice mazes. Simply speaking, in the former game one has to roll blocks through a maze, ending in a particular game situation, and in the latter one, one has to move tokens of variable speed through a maze following some prescribed directions. It turns out that when the number of blocks or the number of tokens is not restricted (unbounded),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 the problems in question. In this way we improve on a previous PSPACE-completeness result of Buchin and Buchin on rolling block mazes to best possible. Moreover, we also consider bounded variants of these maze games, i.e., when the number of blocks or tokens is bounded by a constant, and prove close relations to variants of graph reachability problems.
Lizenz:
Veröffentlichungsvertrag für Publikationen ohne Print on Demand
