Reference:

Markus Holzer and Stefan Schwoon. Reflections on Reflexion – computational complexity considerations on a puzzle game. In Paolo Ferragina and Roberto Grossi, editors, Proceedings of the Third International Conference on FUN with Algorithms, pages 90–105. Università di Pisa, May 2004.

Abstract:

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.

Suggested BibTeX entry:

@inproceedings{HS04b,
    author = {Markus Holzer and Stefan Schwoon},
    booktitle = {Proceedings of the Third International Conference on FUN with Algorithms},
    editor = {Paolo Ferragina and Roberto Grossi},
    month = {May},
    pages = {90--105},
    publisher = {Universit\`a di Pisa},
    title = {Reflections on {Reflexion} -- Computational Complexity Considerations on a Puzzle Game},
    year = {2004}
}