Games, Puzzles, and Computation

Introduction......Page 10
I Games in General......Page 12
What is a Game?......Page 14
The Constraint Logic Formalism......Page 18
Constraint Graphs......Page 19
Constraint Graph Conversion Techniques......Page 21
Bounded Games......Page 24
P-completeness......Page 25
Unbounded Games......Page 26
PSPACE-completeness......Page 28
Planar Graphs......Page 35
Efficient Reversible Computation......Page 36
One-Player Games (Puzzles)......Page 38
NP-completeness......Page 39
An Alternate Vertex Set......Page 41
Unbounded Games......Page 42
PSPACE-completeness......Page 43
Planar Graphs......Page 47
Protected OR Graphs......Page 49
Configuration-to-Configuration Problem......Page 50
Two-Player Games......Page 52
Bounded Games......Page 53
PSPACE-completeness......Page 54
An Alternate Vertex Set......Page 56
Unbounded Games......Page 57
EXPTIME-completeness......Page 58
No-Repeat Games......Page 61
Team Games......Page 63
Unbounded Games......Page 64
Incorrectness of Existing Results......Page 66
Undecidability......Page 69
Planar Graphs......Page 76
Hierarchies of Complete Problems......Page 77
Games, Physics, and Computation......Page 78
II Games in Particular......Page 81
TipOver......Page 83
NP-completeness......Page 84
Sliding-Block Puzzles......Page 88
PSPACE-completeness......Page 89
PSPACE-completeness......Page 92
PSPACE-completeness......Page 93
Plank Puzzles......Page 94
PSPACE-completeness......Page 95
PSPACE-completeness......Page 98
Rush Hour......Page 100
PSPACE-completeness......Page 101
Triangular Rush Hour......Page 103
Hinged Polygon Dissections......Page 104
Dyson Telescope Game......Page 106
Amazons......Page 107
PSPACE-completeness......Page 108
Konane......Page 111
PSPACE-completeness......Page 112
Cross Purposes......Page 114
PSPACE-completeness......Page 115
Open Problems......Page 120
Summary of Part II......Page 124
Contributions......Page 125
Future Work......Page 126
Basic Definitions......Page 128
Generalizations of Turing Machines......Page 130
List of Complexity Classes Used in this Thesis......Page 133
Satisfiability (SAT).......Page 134
Quantified Boolean Formulas (QBF).......Page 135
Deterministic Constraint Logic Activation Sequences......Page 136