License: 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.2018.7
URN: urn:nbn:de:0030-drops-87988
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8798/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-FUN-2018-7.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2018:8798,
  author =	{Davide Bil{\`o} and Luciano Gual{\`a} and Stefano Leucci and Neeldhara Misra},
  title =	{{On the Complexity of Two Dots for Narrow Boards and Few Colors}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8798},
  URN =		{urn:nbn:de:0030-drops-87988},
  doi =		{10.4230/LIPIcs.FUN.2018.7},
  annote =	{Keywords: puzzle, NP-complete, perfect information, combinatorial game theory}
}

Keywords: puzzle, NP-complete, perfect information, combinatorial game theory
Collection: 9th International Conference on Fun with Algorithms (FUN 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI