Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.24
URN: urn:nbn:de:0030-drops-58831
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5883/
Misra, Neeldhara
Two Dots is NP-complete
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{misra:LIPIcs:2016:5883,
author = {Neeldhara Misra},
title = {{Two Dots is NP-complete}},
booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)},
pages = {24:1--24:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-005-7},
ISSN = {1868-8969},
year = {2016},
volume = {49},
editor = {Erik D. Demaine and Fabrizio Grandoni},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5883},
URN = {urn:nbn:de:0030-drops-58831},
doi = {10.4230/LIPIcs.FUN.2016.24},
annote = {Keywords: combinatorial game theory, NP-complete, perfect information, puzzle}
}
| Keywords: | combinatorial game theory, NP-complete, perfect information, puzzle | |
| Seminar: | 8th International Conference on Fun with Algorithms (FUN 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 02.06.2016 |
