Document Open Access Logo

On the Complexity of Two Dots for Narrow Boards and Few Colors

Authors Davide Bilò , Luciano Gualà , Stefano Leucci , Neeldhara Misra

PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.7.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Davide Bilò
  • University of Sassari, Italy
Luciano Gualà
  • University of Rome "Tor Vergata", Italy
Stefano Leucci
  • ETH Zürich, Switzerland
Neeldhara Misra
  • Indian Institute of Technology, Gandhinagar

Cite As Get BibTex

Davide Bilò, Luciano Gualà, Stefano Leucci, and Neeldhara Misra. On the Complexity of Two Dots for Narrow Boards and Few Colors. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.7

Abstract

Two Dots is a popular single-player puzzle video game for iOS and Android. A level of this game consists of a grid of colored dots. The player connects two or more adjacent dots, removing them from the grid and causing the remaining dots to fall, as if influenced by gravity. One special move, which is frequently a game-changer, consists of connecting a cycle of dots: this removes all the dots of the given color from the grid. The goal is to remove a certain number of dots of each color using a limited number of moves. The computational complexity of Two Dots has already been addressed in [Misra, FUN 2016], where it has been shown that the general version of the problem is NP-complete. Unfortunately, the known reductions produce Two Dots levels having both a large number of colors and many columns. This does not completely match the spirit of the game, where, on the one hand, only few colors are allowed, and on the other hand, the grid of the game has only a constant number of columns. In this paper, we partially fill this gap by assessing the computational complexity of Two Dots instances having a small number of colors or columns. More precisely, we show that Two Dots is hard even for instances involving only 3 colors or 2 columns. As a contrast, we also prove that the problem can be solved in polynomial-time on single-column instances with a constant number of goals.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • puzzle
  • NP-complete
  • perfect information
  • combinatorial game theory

Metrics

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

References

  1. Aaron B. Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, and Blair D. Sullivan. Zig-zag numberlink is np-complete. JIP, 23(3):239-245, 2015. URL: http://dx.doi.org/10.2197/ipsjjip.23.239.
  2. Aviv Adler, Erik D Demaine, Adam Hesterberg, Quanquan Liu, and Mikhail Rudoy. Clickomania is hard, even with two colors and columns. The Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity, 2:325, 2017. Google Scholar
  3. Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Trainyard is np-hard. Theoretical Computer Science, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.09.039.
  4. Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, and J. Ian Munro. The complexity of clickomania. CoRR, cs.CC/0107031, 2001. URL: http://arxiv.org/abs/cs.CC/0107031.
  5. Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell. Tetris is hard, even to approximate. Int. J. Comput. Geometry Appl., 14(1-2):41-68, 2004. URL: http://dx.doi.org/10.1142/S0218195904001354.
  6. Kyle Burke, Erik D. Demaine, Harrison Gregg, Robert A. Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Jody Leonard, Maarten Löffler, Aaron Santiago, Christiane Schmidt, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Single-player and two-player buttons & scissors games - (extended abstract). In Jin Akiyama, Hiro Ito, Toshinori Sakai, and Yushi Uno, editors, Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015, Revised Selected Papers, volume 9943 of Lecture Notes in Computer Science, pages 60-72. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-48532-4_6.
  7. Davide Eppstein. Computational complexity of games and puzzles. https://www.ics.uci.edu/ eppstein/cgt/hard.html, accessed on the 23rd of February 2018. Google Scholar
  8. Henning Fernau, Torben Hagerup, Naomi Nishimura, Prabhakar Ragde, and Klaus Reinhardt. On the parameterized complexity of the generalized rush hour puzzle. In Proceedings of the 15th Canadian Conference on Computational Geometry, CCCG'03, Halifax, Canada, August 11-13, 2003, pages 6-9, 2003. URL: http://www.cccg.ca/proceedings/2003/22.pdf.
  9. Gary William Flake and Eric B. Baum. Rush hour is pspace-complete, or "why you should generously tip parking lot attendants". Theor. Comput. Sci., 270(1-2):895-911, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00173-6.
  10. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  11. Harrison Gregg, Jody Leonard, Aaron Santiago, and Aaron Williams. Buttons & scissors is np-complete. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10-12, 2015. Queen’s University, Ontario, Canada, 2015. URL: http://research.cs.queensu.ca/cccg2015/CCCG15-papers/48.pdf.
  12. Luciano Gualà, Stefano Leucci, and Emanuele Natale. Bejeweled, candy crush and other match-three games are (np-)hard. In 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014, pages 1-8. IEEE, 2014. URL: http://dx.doi.org/10.1109/CIG.2014.6932866.
  13. Luciano Gualà, Stefano Leucci, Emanuele Natale, and Roberto Tauraso. Large peg-army maneuvers. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 18:1-18:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.18.
  14. Robert A. Hearn and Erik D. Demaine. Games, puzzles and computation. A K Peters, 2009. Google Scholar
  15. Stefan Langerman and Yushi Uno. Threes!, fives, 1024!, and 2048 are hard. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 22:1-22:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.22.
  16. Neeldhara Misra. Two dots is np-complete. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 24:1-24:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.24.
  17. Daniel Ratner and Manfred K. Warmuth. Nxn puzzle and related relocation problem. J. Symb. Comput., 10(2):111-138, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80001-6.
  18. Ryuhei Uehara and Shigeki Iwata. Generalized Hi-Q is NP-complete. IEICE Transactions (1976-1990), 73(2):270-273, 1990. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact