2015/06/28 by Erik D. Demaine, Stefan Langerman, Demaine, Erik D. +1
Computer Science · Psychology · Social Sciences · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Digital Games and Media #FOS: Computer and information sciences #Gambling Behavior and Treatments
paper · pdf · doi:10.48550/arxiv.1506.08409
openalex publication_date 2015/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.