mia*_*t17 16 algorithm minesweeper
我正在设计类似扫雷的游戏(带有修改过的规则),我想阻止玩家猜测.我的目标是:生成的棋盘上只有很少的显示方块,玩家可以毫无猜测地解决整个拼图.
维基百科提到:
Minesweeper的一些实现将通过从未在显示的第一个方块上放置一个矿,或者通过安排板以使解决方案不需要猜测来设置板.
但是,我无法弄清楚算法.
此外,在另一个StackOverflow问题:扫雷解决算法
改进:在生成器旁边运行求解器,确保拼图具有独特的解决方案.这需要一些聪明,并且在大多数变体中都没有.
我怀疑这是否真的有效.众所周知,解决扫雷是NP完全的.
总之,我的问题是:
dus*_*uff 15
在Simon Tatham的便携式拼图系列中实现扫雷是无猜测的.(它也是MIT许可的,所以如果你愿意,你可以自由复制他的实现.)
众所周知,解决扫雷是NP完全的.
这是事实,但也许并不像你想象的那么重要.所提出的算法类似于"在计算机可以解决之前重复生成随机板".NP-硬度是最坏情况下的特性,但在这里我们真的对平均硬度感兴趣.如果生成了异常硬的电路板,我们可以将求解器超时并使用新电路板重新启动.
而且,即使有一个神谕来区分好板和坏板,你真的希望用户必须解决一个难题才能避免猜测吗？一个不太有才华的计算机解决方案可能会偏向于更公平的董事会.