Erik Demaine's Combinatorial Games:

Clickomania

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 collection of squares connected along edges that all have the same color. At any step, the player can select (click) any group of size at least two. This move causes those blocks to disappear, and any blocks stacked above them fall straight down as far as they can. This falling is similar to Tetris, but each column falls independently. In particular, we never leave an internal hole. One final twist on the rules is that, if an entire column becomes empty of blocks, then the left and right components are slid together to remove the vertical hole.

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.

Our Results

Our paper “The Complexity of Clickomania” proves the following results. The paper is currently available in slightly reduced form (omitting the details of the hardness proofs) as it appears in the book More Games of No Chance, which is a proceedings from the MSRI Combinatorial Game Theory Research Workshop (July 2000). Stay tuned for a full technical report.

The decision version is NP-complete even for just 3 colors and 5 columns.
The decision version is NP-complete even for just 3 columns and 5 colors.
The one-column decision version can be solved in O(k n³) time, where n is the number of blocks and k is the number of colors. This result is based on designing a context-free grammar that generates the solvable puzzles.
The one-column optimization version can be solved in O(k n⁵) time.
The one-column two-color decision version can be solved in O(n) time.
The one-column two-color optimization version can be solved in O(n³).

History

The origins of Clickomania seem unknown. We were introduced to the game by Bernie Cosell in a June 2, 2000 email to the math-fun mailing list. He suggested analyzing the strategy involved in the game. In a followup email, Henry Baker suggested the idea of looking at a small constant number of colors. In another followup email, Michael Kleber pointed out that the game is also known under the title ``Same Game''.

Clickomania! is implemented by Matthias Schuessler in a freeware program for Windows. On the add-ons page, you can find versions for the Macintosh, Java, DOS, Game Boy, and the Palm. There is even a ``solver'' for the Windows version, which appears to be based on a constant-depth lookahead heuristic.

Last updated November 28, 2010 by Erik Demaine. — Accessibility