PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

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 [Theoret. Comput. Sci. 270(1-2) (2002) 895]. We illustrate the importance of our model of computation by giving simple reductions to show that several 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 (I x 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 [Theoret. Comput, Sci. 270(1-2) (2002) 895], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [Int. J. Robot. Res. 3(4) (1984) 76.], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [In: Proc. Internat. Conf. on Fun with Algorithms, Elba. Italy, June 1998, pp. 65-76.], by showing that it is PSPACE-complete even if no barriers are allowed. (c) 2005 Elsevier B.V. All rights reserved.