 Two Dots

Collect colored dots arranged in a rectangular board by drawing monochromatic paths. Description

A simplified version of the game is as follows: the board consists of a $n \times m$ grid in which each position is either empty or occupied by a dot having one out of $k$ colors. Dots are attracted towards the last row as if affected by gravity (i.e., in each colum all the non-empty locations are contiguos and on the last rows). A move consists of either:

• Drawing a monochromatic simple path by connecting together adjacent dots. This causes all the dots of the path to be removed from the board.

• Drawing a monochromatic cycle with a (possibly empty) hanging path. This causes all the dots of cycle’s color to be removed from the board.

After each move, the remaining dots fall down to fill the now-empty locations.

There are $g$ goals $(c_1, t_1), \dots, (c_g, t_g)$ to be satisfied: each goal $(c_i, t_i)$ consists of a color $c_i$ and a positive integer $t_i$. A goal $(c_i, t_i)$ is satisfied when at least $t_i$ dots of color $c_i$ are collected.

The game is won if the player satisfies all $g$ goals within certain number $\ell$ of moves.

Computational complexity

Determining whether there exists a winning strategy is NP-Complete even in the following special cases :

• $k=3$, $\ell=2$, $g=2$ via a reduction from Exact Cover by 3-Sets. An interactive version of the reduction is available here.

• $m=2, \ell=\infty$, and the only goal ($g=1$) is collecting two dots of a single color ($t_1=2)$.

• $n=2$.

The same problem is $W[ 1 ]$-hard when parametrized by $\ell$ , and is in P if (i) $n=1$, or (ii) $m=1$ and $g = O(1)$ .

 D. Bilò, L. Gualà, S. Leucci, N. Misra, “On the Complexity of Two Dots for Narrow Boards and Few Colors”, in FUN 2018.

 Neeldhara Misra, “Two dots is NP-complete”, in FUN 2016.