Paper by Erik D. Demaine

Reference:

Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, and J. Ian Munro, “The Complexity of Clickomania”, in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 389–404, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

BibTeX

@InCollection{ClickomaniaGameTheory2000,
  AUTHOR        = {Therese C. Biedl and Erik D. Demaine and Martin L. Demaine
                   and Rudolf Fleischer and Lars Jacobsen and J. Ian Munro},
  TITLE         = {The Complexity of {Clickomania}},
  BOOKTITLE     = {More Games of No Chance},
  BOOKURL       = {http://www.msri.org/publications/books/Book42/},
  PUBLISHER     = {Cambridge University Press},
  EDITOR        = {R. J. Nowakowski},
  YEAR          = 2002,
  PAGES         = {389--404},
  NOTE          = {Collection of papers from the MSRI Combinatorial Game Theory
                   Research Workshop, Berkeley, California, July 24--28, 2000.},

  LENGTH        = {15 pages},
  COMMENTS      = {This paper is also available as
                   <A HREF="http://arXiv.org/abs/cs.CC/0107031">
                   arXiv:cs.CC/0107031</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.
                   <P>
                   The paper is also available from the
                   <A HREF="http://www.msri.org/publications/books/Book42/contents.html">book's website</A>
                   as <A HREF="http://www.msri.org/publications/books/Book42/files/biedl.ps.gz">http://www.msri.org/publications/books/Book42/files/biedl.ps.gz</A>.}
}

Abstract:

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.

Comments:

This paper is also available as arXiv:cs.CC/0107031 of the Computing Research Repository (CoRR).

The paper is also available from the book's website as http://www.msri.org/publications/books/Book42/files/biedl.ps.gz.

Length:

The paper is 15 pages.

Availability:

The paper is available in PostScript (295k) and gzipped PostScript (108k).

See information on file formats.

[Google Scholar search]