针对不同的棋盘大小,有人计算了在不同地雷密度情况下获胜的概率。三角形对应的曲线为初级 8�8,正方形为 15�13,菱形为高级,30�16。这里的能否求解实际上不包括第一次随机点击的时候踩中雷的概率。[12]
我们把流体通过多孔介质逾渗的模型抽象出来的话,其实对应着点逾渗,也就是把整个介质想象成一个网络,流体在经过每个网格时,有概率 p 的可能通过。如果不能流过的网格在网络中连成了片,流体就不能流过了。
不严格地来说,求解扫雷问题其实和逾渗模型很类似,我们求解的过程其实也像推土机一样 ,不断地利用已有的知识将已知区域向外一层一层地推进。如果游戏中某处雷的密度越大,那么越有可能出现可解部分被雷分开的情况,地雷密度和逾渗参数起到了一样的作用 。如果被分隔到无法连接整个棋盘,那就无法继续推理了。更为严格的证明可以参考 Elchanan Mossel 的论文。[13]
推土机,图片来自网络
随着网格的不断增大,这条胜率曲线中间部分也变得越来越陡峭,扫雷问题越来越向两个极端发展:要不就根本解不出来,要不就是很容易地就能解出来。 在高级模式下,地雷的密度其实已经到了 99/480 = 0.2,能够解出来的概率已经不到 1/4,这还不算手抖了点错了,开局不好重开之类的情况,真的不算是友好了。
结 论
Conclusion
emoji 版本扫雷 [14]
相信看到这里的人
一定已经跃跃欲试 想要玩一下扫雷了
我相信你们
天下无难事,只要肯放弃
卸载也行