The Complexity of Flood Filling Games
The Complexity of Flood Filling Games
复制标题
洪水填充游戏的复杂性
DOI：
10.1007/s00224-011-9339-2
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
Clifford R
中科院分区：
文献类型：
--
作者：
Clifford R
我们研究了流行的单人组合游戏Flood-It的复杂性。在这个游戏中，玩家被赋予一个n × n的方块，每个方块被分配一种颜色。目标是通过尽可能短的泛色操作序列使所有瓷砖的颜色相等。在标准版本中，泛洪操作包括玩家选择一个colourk，然后改变连接到左上方tile tok的单色区域中所有瓷砖的颜色。在执行此操作之后，已经具有所选颜色的相邻区域也将被连接，从而扩展板的单色区域。我们证明了寻找最小洪泛操作次数是NP-难力c ≥3，并且当玩家可以从棋盘上的任何位置执行洪泛操作时，这也成立。然而，我们表明，这种“自由”的变体是在Pforc =2。我们还证明了，对于一个无限数量的颜色，洪水，它crossNP-硬板的高度至少为3，但在P板的高度为2。接下来，我们将展示如何导出（c-1）近似和随机2c/3近似算法，并且除非P =NP，否则不存在与c无关的多项式时间常数因子近似算法。然后，我们调查“要求最高”的n x n个板（需要最多动作的板）需要多少动作，并表明该数量的增长速度与。最后，我们考虑了随机选择瓷砖颜色的棋盘，并表明forc≥2，淹没整个棋盘所需的移动次数是Ω（n），概率很高。
We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given ann×nboard of tiles where each tile is allocated one ofccolours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colourk, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile tok. After this operation has been performed, neighbouring regions which are already of the chosen colourkwill then also become connected, thereby extending the monochromatic region of the board. We show that finding the minimum number of flooding operations isNP-hard forc≥3 and that this even holds when the player can perform flooding operations from any position on the board. However, we show that this ‘free’ variant is inPforc=2. We also prove that for an unbounded number of colours, Flood-It remainsNP-hard for boards of height at least 3, but is inPfor boards of height 2. Next we show how a (c−1) approximation and a randomised 2c/3 approximation algorithm can be derived, and that no polynomial time constant factor, independent ofc, approximation algorithm exists unlessP=NP. We then investigate how many moves are required for the ‘most demanding’n×nboards (those requiring the most moves) and show that the number grows as fast as. Finally, we consider boards where the colours of the tiles are chosen at random and show that forc≥2, the number of moves required to flood the whole board is Ω(n) with high probability.
登录
查看更多内容
DOI：
10.1006/jctb.2001.2045
发表时间：
1999-11
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Eli Berger
通讯作者：
Eli Berger
动态垄断的规模界限
影响因子：
1.1
作者：
D. Peleg
通讯作者：
D. Peleg
$mathbb{Z}^d$ 随机着色的第一通道渗透
DOI：
--
发表时间：
1993
期刊：
影响因子：
--
作者：
L. Fontes;C. Newman
通讯作者：
C. Newman
界面密度：一个新的首次通过问题
影响因子：
1
作者：
L. Chayes;C. Winfield
通讯作者：
C. Winfield
Clickomania 的复杂性
DOI：
--
发表时间：
2001
期刊：
arXiv.org
影响因子：
--
作者：
T. Biedl;E. Demaine;M. Demaine;R. Fleischer;Lars Jacobsen;J. Munro
通讯作者：
J. Munro