按年被提到
20102011 · 1 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:1001.4420 · cs.DS

The Complexity of Flood Filling Games

洪水填充游戏的复杂度
Raphael Clifford, Markus Jalsenius, Ashley Montanaro, Benjamin Sach · 2010

证明 Flood-It 在三色及以上时 NP 难,并给出近似算法与步数界

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2011-08-15 · 最近 2022-02-04发表于 Theory of Computing Systems
3不同的人
3活跃月份
3讨论串
18被引(OpenAlex)

论文研究单人益智游戏 Flood-It:求把整块棋盘变成同一种颜色所需的最少填充次数。作者证明当颜色数 c≥3 时该问题 NP 难,c=2 的“自由”变体属于 P,并给出 c-1 近似和随机化的 2c/3 近似算法,同时证明除非 P=NP 否则不存在与 c 无关的常数因子多项式近似。他们还分析了最难棋盘所需的步数增长,以及随机棋盘需要的步数下界为 Ω(n)。

HN 为什么提它

评论者把它当作洪水填充类游戏是 NP 难问题的依据,推荐给对 Flood-It 感兴趣的人。

其他难度 3 / 5约 75 分钟经得起时间
读之前最好知道
1NP 难与计算复杂度
2近似算法(approximation algorithms)
3图的连通分量
4概率方法基础

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用jnazario · 2014-03

“see this research:”

引这项研究作为洪水填充游戏是 NP-hard 的依据
What is the optimal algorithm for the game 2048?原评论 ↗
引用smnscu · 2022-02

“Bonus, a paper on flood-it: The Complexity of Flood Filling Games”

额外补充一篇关于 Flood-It 游戏复杂度的论文
Assimilate: A Flood-It game for Mac OS 9, released in 2021原评论 ↗
被提交为 story · 1 次