pipette
ESEspañol

Puzznic is PSPACE-Complete

Jake Anderson, Lars Magnus Hvattum, Andr\'as Z. Salamon

Preprint

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