# 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*^{3}) 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*^{5}) 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*^{3}).

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