Sau*_*ani 19 algorithm minesweeper
我很确定大多数人都知道扫雷游戏.我想编码(在C#中)我自己的扫雷游戏,并且正在寻找一些关于该游戏的优秀算法的输入.我一直在浏览网页很长一段时间,但找不到一个好的解决方案.任何人都可以帮助我吗？
Jos*_*Lee 50
生成网格很简单.在执行玩家的移动时,您需要几个简单的算法,以确定打开哪个方块以及它们是丢失还是赢了.
最简单的算法是随机放置所有地雷.(确保你没有重叠!)
问题:玩家的第一次点击可能是我的.
改进:延迟网格的生成,直到用户点击第一个方格,并且不在该方格中放置任何地雷.
问题:玩家的第一次点击可能会显示一个非零数字,他们将被迫随意点击,直到某些东西打开.
改进:在第一次点击周围的(最多)八个方格中也不要产生任何地雷.
问题:玩家可能被迫在某个时候猜测,这使得这成为一个逻辑难题的悲伤借口.
改进:在生成器旁边运行求解器,确保拼图具有独特的解决方案.这需要一些聪明,并且在大多数变体中都没有.
解决歧义的另一种不太常见的方法是检测玩家何时知道他们在同等可能的可能性之间进行选择并将"波形"折叠到他们决定的位置.我从来没有见过这个,但它会很有趣.
除了标记旗帜外,玩家还可以进行两种动作来尝试发现方块:
单一猜测:玩家点击状态未知且没有旗帜的广场.显示广场,看看玩家是否死亡,并在其中放入一个数字.如果正方形包含0,则对所有周围的正方形递归重复.这应该在一个专用函数中,将它与GUI的事件处理程序分开,以使递归变得容易,并且因为它在多个集合中被重用.
Multiguess:玩家点击一个未被发现且已知安全的广场.如果周围的标志数等于此正方形中的数字,我们使用与上面相同的程序打开未标记的正方形.
如果掩盖的方格数与地雷数相同,那么即使玩家没有在每个方格上放置旗帜,玩家也会获胜.
当玩家输掉时,习惯上标记他们所做的任何不正确的猜测,剩余的地雷以及他们踩到的地雷.
正如亨利提到的，解决扫雷问题的正确方法是使用数学，特别是确定性部分的线性代数矩阵数学。我在这里有一整篇文章：
您可以在这里看到所有内容：https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/
我建议通读一遍，然后好好思考一下。Minsweeper 的概率部分也可以使用统计来解决，但我还没有一个好的计划。然而，其他人也对此进行了研究。
如果您尝试编写求解器,我只想添加以下内容 - Minesweeper是NP完成(归档链接).这意味着,除非有人证明P = NP,否则在某些情况下你可以做更好的事情,然后在某些情况下执行强力搜索(但也许游戏对于小字段来说不是NP完成).
| 归档时间： |
|
| 查看次数： |
43737 次 |
| 最近记录： |