The Complexity of Clickomania
The Complexity of Clickomania
复制标题
Clickomania 的复杂性
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Munro
中科院分区：
文献类型：
--
作者：
T. Biedl;E. Demaine;M. Demaine;R. Fleischer;Lars Jacobsen;J. Munro
我们研究了一个流行的益智游戏，被称为Clickomania和Same Game。基本上，一个矩形网格的方块最初是用一些颜色着色的，玩家反复删除一个选定的连接的单色组，其中至少有两个方块，它上面的任何方块都会掉下来。我们表明，一列难题可以解决，即，对于两种颜色，可以在线性时间内去除最大可能数量的块，而对于任意数量的颜色，可以在多项式时间内去除最大可能数量的块。另一方面，对于两列和五种颜色，或者五列和三种颜色，决定一个谜题是否可解（所有的方块都可以被移除）是NP完全的。
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.