The complexity of escaping labyrinths and enchanted forests

Florian D. Schwahn, Clemens Thielen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


The board games The aMAZEing Labyrinth (or simply Labyrinth for short) and Enchanted Forest published by Ravensburger are seemingly simple family games. In Labyrinth, the players move though a labyrinth in order to collect specific items. To do so, they shift the tiles making up the labyrinth in order to open up new paths (and, at the same time, close paths for their opponents). We show that, even without any opponents, determining a shortest path (i.e., a path using the minimum possible number of turns) to the next desired item in the labyrinth is strongly NP-hard. Moreover, we show that, when competing with another player, deciding whether there exists a strategy that guarantees to reach one's next item faster than one's opponent is PSPACE-hard. In Enchanted Forest, items are hidden under specific trees and the objective of the players is to report their locations to the king in his castle. Movements are performed by rolling two dice, resulting in two numbers of fields one has to move, where each of the two movements must be executed consecutively in one direction (but the player can choose the order in which the two movements are performed). Here, we provide an efficient polynomial-time algorithm for computing a shortest path between two fields on the board for a given sequence of die rolls, which also has implications for the complexity of problems the players face in the game when future die rolls are unknown.

Original languageEnglish
Title of host publication9th International Conference on Fun with Algorithms, FUN 2018
EditorsGiuseppe Prencipe, Hiro Ito, Stefano Leonardi, Linda Pagli
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages2713
ISBN (Electronic)9783959770675
StatePublished - 1 Jun 2018
Externally publishedYes
Event9th International Conference on Fun with Algorithms, FUN 2018 - La Maddalena Island, Italy
Duration: 13 Jun 201815 Jun 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference9th International Conference on Fun with Algorithms, FUN 2018
CityLa Maddalena Island


  • Board games
  • Combinatorial game theory
  • Computational complexity


Dive into the research topics of 'The complexity of escaping labyrinths and enchanted forests'. Together they form a unique fingerprint.

Cite this