如何最佳地解决洪水填充难题? [英] How to optimally solve the flood fill puzzle?

问题描述

我喜欢玩益智游戏 Flood-It，可以在线玩:

I like playing the puzzle game Flood-It, which can be played online at:

https://www.lemoda.net/javascript/flood-it/game.html

它还可以作为 iGoogle 小工具使用.目的是用最少的连续充填次数填满整个棋盘.

It's also available as an iGoogle gadget. The aim is to fill the whole board with the least number of successive flood-fills.

我正在尝试编写一个可以最佳解决这个难题的程序.解决这个问题的最佳方法是什么?理想情况下，我想使用 A* 算法，但我不知道估计剩余步数的函数应该是什么.我确实编写了一个程序，该程序进行了深度 4 蛮力搜索以最大化填充区域.它运行得相当好，并且在解决难题方面击败了我，但我对该算法并不完全满意.

I'm trying to write a program which can solve this puzzle optimally. What's the best way to approach this problem? Ideally I want to use the A* algorithm, but I have no idea what should be the function estimating the number of steps left. I did write a program which conducted a depth-4 brute force search to maximize the filled area. It worked reasonably well and beat me in solving the puzzle, but I'm not completely satisfied with that algorithm.

有什么建议吗?提前致谢.

Any suggestions? Thanks in advance.

推荐答案

作为一种启发式方法，您可以构建一个图形，其中每个节点代表一组连续的、颜色相同的正方形，并且每个节点都与它接触的那些正方形相连.(每条边的权重为 1).然后，您可以使用寻路算法来计算从左上角到所有其他节点的距离".然后，通过使用其他 5 种颜色中的每一种查看洪水填充的结果，确定哪一种使与最远"节点的距离最小，因为这可能是您的瓶颈.

As a heuristic, you could construct a graph where each node represents a set of contiguous, same-colour squares, and each node is connected to those it touches. (Each edge weighted as 1). You could then use a path-finding algorithm to calculate the "distance" from the top left to all other nodes. Then, by looking the results of flood-filling using each of the other 5 colours, determine which one minimizes the distance to the "furthest" node, since that will likely be your bottleneck.

将该计算的结果与目前完成的填充次数相加，并将其用作您的 A* 启发式.

Add the result of that calculation to the number of fills done so far, and use that as your A* heuristic.

这篇关于如何最佳地解决洪水填充难题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！