ABSTRACT
In this chapter we present the definitions and complexity proofs for Nondeterministic Constraint Logic, both the bounded and unbounded varieties.
Complexity Background. A one-player game is a puzzle: one player makes a series of moves, trying to accomplish some goal. For example, in a slidingblock puzzle, the goal could be to get a particular block to a particular location. We use the terms “puzzle” and “one-player game” interchangeably. For puzzles, the generic forced-win decision question-“does player X have a forced win?”—becomes “is this puzzle solvable?”
