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 [
2].
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™ puzzles are PSPACE-complete [2], of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban
is PSPACE-complete [1], by showing that it is PSPACE-complete even if no barriers are allowed.