Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Stefan Langerman, “Bust-A-Move/Puzzle Bobble is NP-complete”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 94–104.

BibTeX

@InProceedings{BustAMove_JCDCGG2015full,
  AUTHOR        = {Erik D. Demaine and Stefan Langerman},
  TITLE         = {{Bust-A-Move/Puzzle Bobble} is {NP}-complete},
  BOOKTITLE     = {Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015)},
  bookurl       = {http://www.kurims.kyoto-u.ac.jp/~takazawa/JCDCGG2015/},
  ADDRESS       = {Kyoto, Japan},
  MONTH         = {September 14--16},
  YEAR          = 2015,
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 9943,
  PAGES         = {94--104},

  doi           = {https://dx.doi.org/10.1007/978-3-319-48532-4_9},
  dblp          = {https://dblp.org/rec/conf/jcdcg/DemaineL15},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-319-48532-4_9">SpringerLink</A> and as <A HREF="https://arXiv.org/abs/1506.08409">arXiv:1506.08409</A>.},
  replaces      = {BustAMove_JCDCGG2015},
  papers        = {BustAMove_JCDCGG2015},
}

Abstract:

We prove that the classic 1994 Taito video game, known as Puzzle Bobble or Bust-a-Move, is NP-complete. Our proof applies to the perfect-information version where the bubble sequence is known in advance, and it uses just three bubble colors.

Comments:

This paper is also available from SpringerLink and as arXiv:1506.08409.

Availability:

The paper is available in PDF (743k).

See information on file formats.

[Google Scholar search]

Related papers:

BustAMove_JCDCGG2015 (Bust-A-Move/Puzzle Bobble is NP-complete)