百科问答小站 logo
百科问答小站 font logo



根据完全正确的逻辑推理,高级扫雷(99个雷,16*30平铺网络)有解的概率是多少? 第1页

  

user avatar   song-zhu-shi-74 网友的相关建议: 
      

谢邀。本人非数学专业,无法用严格的数学方法进行证明,但对于一局扫雷游戏“有解”的概率,最简单的办法就是借助计算机,写一个自动寻路算法,得到扫雷游戏的统计值。

值得注意的是,扫雷游戏可以严格证明,属于NP-complete(

经典证明:扫雷是NP完全问题

)。本人对此也不算太熟,个人的理解是对于扫雷游戏而言,无法实现一个最优化的求解算法,使得其胜率达到最大值,所以人为编写出的算法,其统计胜率应该会低于极限胜率。根据我自己过往的经验,对于旧版扫雷,计算机跑出来的胜率不超过40%,大概在35%~40%的样子。

另外还要注意的是,旧版扫雷和新版扫雷对于第一下点击的处理是不一样的,Vista之前的版本,第一下点击保证的是点击的那个格不是雷,而Vista之后的版本,第一下不仅保证点击的方块不是雷,还需要保证一个方块周边的八个方块也必定不是雷,这两种情况下,算法的复杂程度显然也是不一样的,后一种情况对于胜率必定有极大的提高。

而且,既然扫雷属于NP完全问题,想要这么简单地得到一个“必定有解”的数学临界值是不可能的。而且对于题主所言的这些临界值假设,我可以很简单地构造出一个例子:只需要三颗雷,就完全可以实现一个无法“必定有解”的情况:

无论你的棋盘多大,雷的数量就需要三颗,如图所示,除了这个区域,其余所有部分都没有雷,但这四个已知区域就足以将确定解的情况封闭,1和3的左边都可能是雷。而当雷的数量为两颗时,显然无论如何排列都不可能构造出封闭的空间(因为有一颗雷必须用来构成不确定选择区域,只靠一颗雷不可能形成封闭空间),对于任何大小的棋盘都必定能有解。

并且,根据第一下点击必定不是地雷的规定,我们只需要一个2*3的棋盘,就已经可以实现这个局面。而在默认为矩形的棋盘下,任何维度超过2*3的棋盘,包含三颗雷,无论你第一下点哪里,都有可能生成出上图的局面。即便玩的是新版扫雷,维度超过4*5的棋盘也就不可能避免这种情况的产生,而一般扫雷最小的棋盘也得是初级的8*8。所以只需要3颗雷,就足以使得扫雷游戏不是绝对有解,讨论“必定有解”的临界值是没有意义的。




  

相关话题

  有没有推理小说的作案手法是利用药物副作用来影响人的感官? 
  如何保证扫雷第二步或者第三步是安全的? 
  三个极度嫉妒的人分一个蛋糕,何种策略能让三人都觉得公平? 
  你接到了警察的电话:“你房子外有杀人狂!赶紧锁门,无论对方说什么都不能开门!”这时门外有人喊:? 
  为什么要让工兵费时费力去排除地雷,让一些动物从雷区反复走来走去不就把地雷排光了? 
  如何评价紫金陈的小说? 
  你看过最令人惊艳的诡计是什么? 
  世界上有哪些至今未破的悬案? 
  如今监控遍地,杀手会不会因此绝迹? 
  你最喜欢京极堂系列哪一部,为什么? 

前一个讨论
代斯勒到底有多「天才」?
下一个讨论
除了暴风雪山庄模式,现代本格派推理真的无路可走了吗?





© 2024-11-24 - tinynew.org. All Rights Reserved.
© 2024-11-24 - tinynew.org. 保留所有权利