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.