Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

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

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