PSPACE-completeness of Bloxorz, and of games with 2-buttons

T.C. van der Zanden, H.L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)

Abstract

Bloxorz is an online puzzle game where players move a 1×1×2 block by tilting it on a subset of the two dimensional grid, that also features switches that open and close trapdoors. The puzzle is to move the block from its initial position to an upright position on the goal square. We show that the problem of deciding whether a given Bloxorz level is solvable is PSPACE-complete and that this remains so even when all trapdoors are initially closed or all trapdoors are initially open. We also answer an open question of Viglietta [6], showing that 2-buttons are sufficient for PSPACE-hardness of general puzzle games. We also examine the hardness of some variants of Bloxorz, including variants where the block is a 1×1×1 cube, and variants with single-use tiles.
Original languageEnglish
Title of host publicationAlgorithms and Complexity (9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings)
EditorsV.Th. Paschos, P. Widmayer
Place of PublicationBerlin
PublisherSpringer
Pages403-415
ISBN (Print)978-3-319-18172-1
DOIs
Publication statusPublished - 2015
Event9th International Conference on Algorithms and Complexity (CIAC 2015), May 20-22, 2015, Paris, France - Paris-Dauphine University, Paris, France
Duration: 20 May 201522 May 2015

Publication series

NameLecture Notes in Computer Science
Volume9079
ISSN (Print)0302-9743

Conference

Conference9th International Conference on Algorithms and Complexity (CIAC 2015), May 20-22, 2015, Paris, France
Abbreviated titleCIAC 2015
Country/TerritoryFrance
CityParis
Period20/05/1522/05/15

Fingerprint

Dive into the research topics of 'PSPACE-completeness of Bloxorz, and of games with 2-buttons'. Together they form a unique fingerprint.

Cite this