Abstract:
The computational complexity of several combinatorial puzzles has been determined in the liter-ature in the past few decades. We introduce the non-deterministic constraint logic (NCL) in this paper. As an application, we prove that Beanstalk, a Sokoban-like puzzle, is PSPACE-complete by reduction from NCL.