我喜欢玩益智游戏 Flood-It，可以在线玩：
https://www.lemoda.net/javascript/flood-it/game.html
它也可以作为 iGoogle 小工具使用。目的是用最少数量的连续洪水填充来填充整个电路板。
我正在尝试编写一个可以最佳解决这个难题的程序。解决这个问题的最佳方法是什么？理想情况下，我想使用A*算法，但我不知道估计剩余步数的函数应该是什么。我确实编写了一个程序，该程序进行了深度 4 蛮力搜索以最大化填充区域。它工作得相当好，在解决难题方面击败了我，但我对那个算法并不完全满意。
有什么建议么？提前致谢。
作为一种启发式方法，您可以构建一个图，其中每个节点代表一组连续的、相同颜色的正方形，并且每个节点都连接到它所接触的那些。（每条边的权重为 1）。然后，您可以使用寻路算法来计算从左上角到所有其他节点的“距离”。然后，通过使用其他 5 种颜色中的每一种来查看洪水填充的结果，确定哪一种使与“最远”节点的距离最小，因为那可能是您的瓶颈。
将该计算的结果添加到到目前为止完成的填充数中，并将其用作您的 A* 启发式。
一个天真的“贪婪”算法是选择最大化主要区域的整体周长的下一步。
（我的几个聪明的朋友前几天正在考虑这个问题，并决定优化可能是 NP 难的（例如你必须蛮力它） - 我不知道他们是否正确（没有听到推理，我自己还没有考虑过）。）
请注意，对于计算步骤，我认为联合查找算法是您的朋友，它使计算“一步”非常快（参见例如这篇博文）。
玩了几次游戏后，我注意到一个好的策略是始终“深入”，去寻找最深入未淹没区域的颜色。
A* 只是一个优先的图搜索。每个节点都是一个游戏状态，您根据一些启发式对节点进行排名，并始终扩展最低预期最终成本节点。只要您的启发式方法没有低估成本，您找到的第一个解决方案就可以保证是最优的。
玩了几次游戏后，我发现尝试钻到对面的角落然后所有的角落往往会导致胜利。因此，一个好的起始成本估算将是（到目前为止的成本）+足够数量的填充以到达对角[注意：不是最低限度，就足够了。只是贪婪地填充角落以计算启发式]。
这是实现图形以支持Smashery 启发式的想法。
表示不相交集合中的每组连续的、相同颜色的正方形，以及相邻正方形组的列表。泛洪填充将一个集合与其所有相邻集合合并，并合并邻接列表。这种隐式图结构将让您找到从左上角到最远节点的距离。
Smashery 的答案可以稍作调整。对于移动总数估计，如果在最大距离处有“k”种颜色，则将“k-1”添加到移动估计数。
更一般地，对于每种颜色，考虑可以清除颜色的最大距离。这为我们提供了一个字典，将一些最大距离映射到可以在该距离清除的非零颜色数。对键求和 value-1 并将其添加到最大距离以获得移动次数估计。
此外，还有一些免费案例。如果在任何时候我们可以在一个动作中清除一种颜色，我们就可以在不考虑其他动作的情况下进行该动作。
我一直在研究这个，在我的求解器工作后，我看看其他人采取的方法。
那里的大多数求解器都是启发式的，不能保证最优性。启发式方法着眼于未选择的方格数量和颜色分布，或到“最远”方格的距离。将良好的启发式方法与有界 DFS（或带前瞻的 BFS）相结合，可以得到对于标准 14x14 网格相当快的解决方案。
我采取了一种稍微不同的方法，因为我有兴趣找到可证明的最佳路径，而不仅仅是一条“好”的路径。我观察到搜索空间实际上比搜索树的分支因子增长得慢得多，因为有很多重复的位置。（因此，对于深度优先策略，保持历史记录以避免重复工作很重要。）有效分支因子似乎更接近 3 而不是 5。
我采用的搜索策略是将 BFS 执行到“中点”深度，在该深度中，状态的数量将变得不可行，最好在 11 到 13 步之间进行。然后，我在中点深度检查每个状态，并以该状态作为根开始执行新的 BFS。这两种 BFS 搜索都可以通过消除在先前深度中找到的状态来修剪，而后一种搜索可以受最知名解决方案的深度限制。（应用于第二步中检查的子树顺序的启发式方法也可能会有所帮助。）
另一种被证明是快速求解器关键的修剪技术是简单地检查是否有超过 N 种颜色，如果您距离当前最佳解决方案只有 N 步或更少步。
一旦我们知道哪个中点状态在通往最佳解决方案的路径上，程序就可以使用该中点状态作为目标执行 DFS（并修剪选择不在中点的正方形的任何路径。）或者，它可能是可行的在 BFS 步骤中构建路径，代价是一些额外的内存。
我的求解器速度不是很快，但它可以在几分钟内找到有保证的最优解。（参见http://markgritt.livejournal.com/673948.html或http://pastebin.com/ZcrS286b上的代码。）
我认为您可以考虑匹配或不匹配当前颜色的正方形数量。因此，您对“距离”的启发式测量将是板上与您选择的颜色不同颜色的方格数，而不是步数。
一个幼稚的启发式方法可能是使用剩余的颜色数（减 1）——这是可以接受的，因为至少需要多次点击才能清除棋盘。
I'm not certain, but I'm fairly sure that this could be solved greedily. You're trying to reduce the number of color fields to 1, so reducing more color fields earlier shouldn't be any less efficient than reducing fewer earlier.
1) Define a collection of existing like-colored groups.
2) For each collection, count the number of neighboring collections by color. The largest count of neighboring collections with a single color is the weight of this collection.
3) Take the collection with the highest count of neighbors with a single color, and fill it to that color. Merge the collections, and update the sort for all the collections affected by the merge (all the new neighbors of the merged collection).
Overall, I think this should actually compute in O(n log n) time, where n is the number of pixels and the log(n) only comes from maintaining the sorted list of weights.
I'm not sure if there needs to be a tie-breaker for when multiple fields have the same weight though. Maybe the tie-breaker goes to the color that's common to the most groups on the map.
Anyway, note that the goal of the game is to reduce the number of distinct color fields and not to maximize the perimeter, as different color schemes can occasionally make a larger field a sub-optimal choice. Consider the field:
3 3 3 3 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
The color 1 has the largest perimeter by any measure, but the color 2 is the optimal choice.
EDIT>
Scratch that. The example:
3 1 3 1 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
Invalidates my own greedy algorithm. But I'm not convinced that this is a simple graph traversal, since changing to a color shared by 2 neighbors visits 2 nodes, and not 1.
Color elimination should probably play some role in the heuristic.
1) It is never correct to fill with a color that is not already on the graph.
2) If there is one color field with a unique color, at least one fill will be required for it. It cannot be bundled with any other fills. I think this means that it's safe to fill it sooner rather than later.
3) The greedy algorithm for neighbor field count makes sense for a 2 color map.