Puzznic is PSPACE-Complete
In the authors' words
We prove that deciding solvability of Puzznic, a falling-block puzzle game originally developed by Taito, is PSPACE-complete. To show hardness we construct a self-closing door gadget using Puzznic's game mechanics. For membership, we show that the configuration space is exponentially bounded and apply Savitch's theorem. We also improve an existing NP-completeness proof for a simpler version of the game known as Cubic, showing that this game is NP-complete even when restricted to only two kinds of blocks.
Main resultThe abstract does not state a limitation.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 15 pages