如何最佳地解决洪水填充难题？

Question

我喜欢玩益智游戏Flood-It,它可以在线播放:

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

它也可以作为iGoogle小工具使用.目的是用最少数量的连续填充填充整个委员会.

我正在尝试编写一个可以最佳地解决这个难题的程序.解决这个问题的最佳方法是什么？理想情况下我想使用A*算法,但我不知道估算剩余步数的功能应该是什么.我写了一个程序,进行了深度4强力搜索,以最大化填充区域.它工作得相当好,并且在解决这个难题时打败了我,但我对这个算法并不完全满意.

有什么建议？提前致谢.

Answer 1

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

将计算结果添加到目前为止完成的填充次数,并将其用作A*启发式.

Answer 2

我认为您可以考虑与当前颜色匹配或不匹配的方块数量。因此，您对“距离”的启发式测量将是棋盘上与您选择的颜色不同颜色的方块数量，而不是步数。