**Reference**:- Robert A. Hearn and Erik D. Demaine, “PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation”,
*Theoretical Computer Science*, volume 343, number 1–2, October 2005, pages 72–96. Special issue ``Game Theory Meets Theoretical Computer Science''. **Abstract**:-
We present a nondeterministic model of computation based on reversing edge
directions in weighted directed graphs with minimum in-flow constraints on
vertices. Deciding whether this simple graph model can be manipulated in
order to reverse the direction of a particular edge is shown to be
PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove
this result in a variety of special cases including planar graphs and highly
restricted vertex configurations, some of which correspond to a kind of
passive constraint logic. Our framework is inspired by (and indeed a
generalization of) the “Generalized Rush Hour Logic” developed by
Flake and Baum [4].
We illustrate the importance of our model of computation by giving simple reductions to show that multiple motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1 × 2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour

^{TM}puzzles are PSPACE-complete [4], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [6], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [2], by showing that it is PSPACE-complete even if no barriers are allowed. **Comments**:- This paper is also available as arXiv:cs.CC/0205005 of the Computing Research Repository (CoRR), and from ScienceDirect.
**Updates**:- Ivars Peterson wrote an article describing these results, “Logic in the Blocks”,
*Science News*162(7):106-108, August 17, 2002. **Availability**:- The paper is available in PDF (372k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- NCL_ICALP2002 (The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications)
- CL_Complexity2008 (Constraint Logic: A Uniform Framework for Modeling Computation as Games)

See also other papers by Erik Demaine.

Last updated May 22, 2016 by Erik Demaine.