The Complexity of Clickomania

Simple item page
dc.creatorBiedl, Therese C.
dc.creatorDemaine, Erik D.
dc.creatorDemaine, Martin L.
dc.creatorFleischer, Rudolf
dc.creatorJacobsen, Lars
dc.creatorMunro, J. Ian
dc.date2001-07-21
dc.date.accessioned2026-07-07T03:17:22Z
dc.date.available2026-07-07T03:17:22Z
dc.descriptionWe 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.
dc.description15 pages, 3 figures. To appear in More Games of No Chance, edited by R. J. Nowakowski
dc.identifierhttps://arxiv.org/abs/cs/0107031
dc.identifierhttp://arxiv.org/abs/cs/0107031
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30701
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectF.2.2; F.1.3; F.1.1; G.2.1
dc.titleThe Complexity of Clickomania
dc.typetext

Files

Collections

arXiv