Games & Complexity

After the inspiring book by Hearn» and Demaine»:
Games, Puzzles, & Computation,
AK. Peters (2009)

IPA Advanced Course on Algorithmics and Complexity
Eindhoven, July 2016. (pdf 2016)

Walter Kosters»
Hendrik Jan Hoogeboom»

1. intro: Games and complexity classes, constraint logic
2. Gadgets, planarity, exercises
3. Tip-Over is NP-complete
4. Rush Hour is PSPACE complete, plank puzzle
5. Wrap-up: other classes of games

Seminar Combinatorial Algorithms

Spring 2011 we hosted a seminar for Leiden Master students on the book. Additionally separate papers were read on the topic of the book, complexity of tilings, puzzles and games.

sponsor area

Rush Hour | TipOver | River Crossing