LIPIcs.FUN.2016.24.pdf
- Filesize: 0.69 MB
- 12 pages
Document
Two Dots is NP-complete
Author
-
Part of:
Volume:
8th International Conference on Fun with Algorithms (FUN 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-02
Cite As Get BibTex
Neeldhara Misra. Two Dots is NP-complete. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.24
Abstract
Two Dots is a popular single-player puzzle video game for iOS and Android. In its simplest form, the game consists of a board with dots of different colors, and a valid move consists of connecting a sequence of adjacent dots of the same color. We say that dots engaged in a move are "hit" by the player. After every move, the connected dots disappear, and the void is filled by new dots (the entire board shifts downwards and new dots appear on top). Typically the game provides a limited number of moves and varying goals (such as hitting a required number of dots of a particular color). We show that the perfect information version of the game (where the sequence of incoming dots is known) is NP-complete, even for fairly restricted goal types.
Subject Classification
Keywords
- combinatorial game theory
- NP-complete
- perfect information
- puzzle
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ahmed Abdelrazek, Aditya Acharya, and Philip Dasler. 2048 without new tiles is still hard. In Proceedings of the 8th International Conference on Fun with Algorithms (To Appear), 2016.
-
Aaron B. Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sanchez Villaamil, and Blair D. Sullivan. Zig-zag numberlink is NP-complete. JIP, 23(3):239-245, 2015.
-
Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Trainyard is NP-hard. In Proceedings of the 8th International Conference on Fun with Algorithms (To Appear), 2016.
-
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
-
Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In MFCS: Symposium on Mathematical Foundations of Computer Science, 2001.
-
Fedor V. Fomin, Pinar Heggernes, and Erik Jan van Leeuwen. Making life easier for firefighters. In Proceedings of the 6th International Conference on Fun with Algorithms, volume 7288, pages 177-188. Springer, 2012.
-
M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.
-
Stefan Langerman and Yushi Uno. Threes!, Fives, 1024!, and 2048 are hard. In Proceedings of the 8th International Conference on Fun with Algorithms (To Appear), 2016.
- Toby Walsh. Candy crush is NP-hard. CoRR, abs/1403.1911, 2014. URL: http://arxiv.org/abs/1403.1911.