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

MIT Hardness Group, Josh Brunner, Lily Chung +4

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,…