Single-Player and Two-Player Buttons & Scissors Games
Files
Publication date
2016
Authors
Burke, Kyle
Demaine, Erik
Gregg, Harrison
Hearn, Robert
Hesterberg, Adam
Hoffman, Michael
Ito, Hiro
Kostitsyna, Irina
Leonard, Jody
Löffler, Maarten
Editors
Advisors
Supervisors
DOI
Document Type
Other
Metadata
Show full item recordCollections
License
Abstract
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C=2 colors but polytime solvable for C=1. Similarly the game is NP-complete if every color is used by at most F=4 buttons but polytime solvable for F≤3. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.
Keywords
CG, GD, PUZ
Citation
Burke, K, Demaine, E, Gregg, H, Hearn, R, Hesterberg, A, Hoffman, M, Ito, H, Kostitsyna, I, Leonard, J, Löffler, M, Schmidt, C, Uehara, R, Uno, Y & Williams, A 2016, Single-Player and Two-Player Buttons & Scissors Games. < http://arXiv.org/abs/1607.01826 >