ABSTRACT

This book is about games people play and puzzles people solve, viewed from the perspective of computer science-in particular computational complexity. Over the years, we have found increasingly deep connections between games, puzzles, and computation. These connections are interesting to us from multiple perspectives. As game players and puzzle solvers, we find underlying mathematical reasons that games and puzzles are challenging, which perhaps explain why they are so much fun. As computer scientists, we find that games and puzzles serve as powerful models of computation, quite different from the usual models of automata and circuits, offering a new way of thinking about computation.