Clickomania (SameGame)

A single player game in which the player removes groups of tiles of the same color in a rectangular board.

Description

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.

Computational complexity

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$.

References

[1] The referenced material may not have undergone a rigorous peer review process (e.g., papers on open-access repositories, personal webpages, extended abstracts, ...) 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.

▸ ▾ Cite this page

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