pipette
ENEnglish

Puzznic is PSPACE-Complete

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 15 pages