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 ( 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 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.