Selected publications by Stefan Schwoon

We investigate the complexity of solving puzzles in the game Reflexion. It is shown that the difficulty of the puzzles depends critically on the features used in the puzzles; the most basic variant of the game is SL-complete, and hence can be solved in polynomial time, whereas other variants are NP- or even PSPACE-complete.

   address = {Isola d'Elba, Italy},
   author = {Holzer, Markus and Schwoon, Stefan},
   booktitle = {{P}roceedings of the 3rd {I}nternational {C}onference on {F}un with {A}lgorithms ({FUN}'04)},
   editor = {Ferragina, Paolo and Grossi, Roberto},
   month = may,
   pages = {90-105},
   publisher = {Edizioni Plus, Universit{\`a} di Pisa},
   title = {Reflections on {R}eflexion~-- Computational Complexity Considerations on a Puzzle Game},
   url = {},
   year = {2004},

About LSV