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

Tom C. Van Der Zanden; Hans L. Bodlaender

doi:10.1007/978-3-319-18173-8_30

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

Tom C. Van Der Zanden^*, Hans L. Bodlaender

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings
Editors	Vangelis Th. Paschos , Peter Widmayer
Publisher	Springer
Pages	403-415
Number of pages	13
ISBN (Electronic)	978-3-319-18173-8
ISBN (Print)	9783319181721
DOIs	https://doi.org/10.1007/978-3-319-18173-8_30
Publication status	Published - 2015
Event	9th International Conference on Algorithms and Complexity, CIAC 2015 - Paris, France Duration: 20 May 2015 → 22 May 2015

Publication series

Name	Lecture Notes in Computer Science
Volume	9079
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Algorithms and Complexity, CIAC 2015
Country/Territory	France
City	Paris
Period	20/05/15 → 22/05/15

Access to Document

10.1007/978-3-319-18173-8_30

chp%3A10.1007%2F978-3-319-18173-8_30Final published version, 337 KBLicence: Taverne

Cite this

Van Der Zanden, T. C., & Bodlaender, H. L. (2015). PSPACE-completeness of Bloxorz and of games with 2-buttons. In V. T. Paschos , & P. Widmayer (Eds.), Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings (pp. 403-415). (Lecture Notes in Computer Science; Vol. 9079). Springer. https://doi.org/10.1007/978-3-319-18173-8_30

@inproceedings{235aefce42d24b8eba546924d115439f,

title = "PSPACE-completeness of Bloxorz and of games with 2-buttons",

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.",

author = "{Van Der Zanden}, {Tom C.} and Bodlaender, {Hans L.}",

year = "2015",

doi = "10.1007/978-3-319-18173-8_30",

language = "English",

isbn = "9783319181721",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "403--415",

editor = "{Paschos }, {Vangelis Th. } and Widmayer, {Peter }",

booktitle = "Algorithms and Complexity",

note = "9th International Conference on Algorithms and Complexity, CIAC 2015 ; Conference date: 20-05-2015 Through 22-05-2015",

}

Van Der Zanden, TC & Bodlaender, HL 2015, PSPACE-completeness of Bloxorz and of games with 2-buttons. in VT Paschos & P Widmayer (eds), Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings. Lecture Notes in Computer Science, vol. 9079, Springer, pp. 403-415, 9th International Conference on Algorithms and Complexity, CIAC 2015, Paris, France, 20/05/15. https://doi.org/10.1007/978-3-319-18173-8_30

PSPACE-completeness of Bloxorz and of games with 2-buttons. / Van Der Zanden, Tom C.; Bodlaender, Hans L.
Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings. ed. / Vangelis Th. Paschos ; Peter Widmayer. Springer, 2015. p. 403-415 (Lecture Notes in Computer Science; Vol. 9079).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Van Der Zanden, Tom C.

AU - Bodlaender, Hans L.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84944727723&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-18173-8_30

DO - 10.1007/978-3-319-18173-8_30

M3 - Conference contribution

AN - SCOPUS:84944727723

SN - 9783319181721

T3 - Lecture Notes in Computer Science

SP - 403

EP - 415

BT - Algorithms and Complexity

A2 - Paschos , Vangelis Th.

A2 - Widmayer, Peter

PB - Springer

T2 - 9th International Conference on Algorithms and Complexity, CIAC 2015

Y2 - 20 May 2015 through 22 May 2015

ER -

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this