Two Dots is NP-complete

Author Neeldhara Misra



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.24.pdf
  • Filesize: 0.69 MB
  • 12 pages

Document Identifiers

Author Details

Neeldhara Misra

Cite AsGet 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.
Keywords
  • combinatorial game theory
  • NP-complete
  • perfect information
  • puzzle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  5. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In MFCS: Symposium on Mathematical Foundations of Computer Science, 2001. Google Scholar
  6. 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. Google Scholar
  7. M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979. Google Scholar
  8. 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. Google Scholar
  9. Toby Walsh. Candy crush is NP-hard. CoRR, abs/1403.1911, 2014. URL: http://arxiv.org/abs/1403.1911.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail