Clickomania is an interactive single player game played on a $n \times m$ grid that can be either empty or colored. Initially each cell is colored with one out of $k$ colors.

The player repeatedly selects a maximal monochromatic set of $2$ or more connected (w.r.t. $4$-adjacency) non-empty cells. The selected cells are then removed from the grid (i.e., they become empty), all the remaining colored cells fall downwards to fill the holes left by the removed cells, and any column consisting of only empty cells is deleted.

The player wins by removing all colored cells.

The problem of deciding whether an instance of Clickomania admits a solution has been considered in [1]. It is:

- Solvable in $O(n)$ time when $m=1$ and $k=2$ .
- Solvable in polynomial time when $m=1$.
- NP-Hard when $m \ge 2$ and $k \ge 5$.
- NP-Hard when $m \ge 5$ and $k \ge 3$.

[1] T. C. Biedl, E. D. Demaine, M. L. Demaine, R. Fleischer, L. Jacobsen, J. I. Munro, “The Complexity of Clickomania “, arXiv:cs/0107031, 2001.

Image courtesy of Matthias Schüssler.

@misc{cog:clickomania, author = "{CoG contributors}", title = "{Clickomania (SameGame) --- Complexity of Games}", year = "2019", url = "https://www.isnphard.com/i/clickomania/", note = "[Online; accessed 2019-11-24]" }