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:

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 [1]:

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

References

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

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