1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete

Josh Brunner, Lily Chung, Erik D. Demaine +4

Consider $n^2-1$ unit-square blocks in an $n\times n$ square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variat…