Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete

Abstract

We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another, given the ability to push up to one block at a time? In particular, we remove the need for fixed (immovable) walls from a 2022 result. This fundamental model of block pushing, introduced in 1999, abstracts the mechanics of many video games. It was shown NP-hard in 2000, but its final complexity remained open for 25 years. Our result uses a new framework for checkable gadgets/gizmos, extending a prior framework for checkable gadgets to handle reconfiguration problems, at the cost of requiring a stronger auxiliary gadget. We also introduce a new connection between the motion-planning-through-gadgets framework (with an agent) and the Graph Orientation Reconfiguration Problem (with no agent), including Nondeterministic Constraint Logic.

34 pages, 20 figures. Improved writing and added intuition