The Complexity of Clickomania
Thérèse Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, Ian Munro · 2002
. We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes a chosen connected monochromatic group of at least two square blocks, and any blocks above it fall down. We show that one-column puzzles can be solved, i.e., the maximum possible number of blocks can be removed, in linear time for two colors, and in polynomial time for an arbitrary number of colors. On the other hand, deciding whether a puzzle is solvable (all blocks can be removed) is NP-complete for two columns and five colors, or five columns and three colors. 1. Introduction Clickomania is a one-player game (puzzle) with the following rules. The board is a rectangular grid. Initially the board is full of square blocks each colored one of k colors. A group is a maximal connected monochromatic polyomino; algorithmically, start with each block as its own group, then repeatedly combine groups of the same color that are adjacent along an edge. At any step, the player can select (click) any group of size at least two. This causes those blocks to disappear, and any blocks stacked above them fall straight down as far as they can (the settling process). Thus, in particular, there is never an internal hole. There is an additional twist on the rules: if an entire column becomes empty of blocks, then this column is “removed,” bringing the two sides closer to each other (the column shifting process). The basic goal of the game is to remove all of the blocks, or to remove as many blocks as possible. Formally, the basic decision question is whether a given puzzle is solvable: can all blocks of the puzzle be removed? More generally, the algorithmic problem is to find the maximum number of blocks that can be removed from a given puzzle. We call these problems the decision and optimization versions of Clickomania. There are several parameters that influence the complexity of Clickomania. One obvious parameter is the number of colors. For example, the problem is trivial if there is only one color, or every block is a different color.