- 首先需要实现的是扫雷游戏本身的游戏逻辑。其中基本操作通过重载可以很容易实现,点到空格块爆出周围的一块的通过遍历周围的格子模拟点击也可以轻松实现。
- 需要注意的是布雷算法,其本质是在C(m,n)种情况中随机选择一个。想要简单高效的实现可以使用洗牌算法,在固定位置放雷然后通过洗牌操作来打乱数组即可。
- 然后在计算概率前首先需要能简单地确定"定雷",也就是一定是雷的格子。依照个人的扫雷经验,首先有一个简单的逻辑,就是一个数字格周围的未翻开格如果等同于他自身的数字,那么这些未翻开格肯定都是雷。如果一个数字格周围的"定雷"数已经等同于他自身的数字,那么他周围的其他未翻开格就一定是"定非雷"。
- 虽然人工扫雷时有更多的简单逻辑,例如看边角,记下几个格子里一定有几个雷来推断,但这些算法不够简单也不一定有效不适合机械计算,故没有采用。
- 但仅凭上述逻辑显然不能标出所有的"定雷"和"定非雷",但也不用去有意标记了因为接下来进行的与概率计算有关操作中会顺带完成。这将在关于扫雷的古典概型基础中详细论述。现在仅仅说结论:计算场上所有未翻开格需要知道所有的可能解。因为计算解的方程过于复杂,所以本人采用最为简单粗暴的方法来列出所有解:穷举。但显然,暴力穷举会产生过多的重复计算,例如不符合游戏规则的解。所以最后采用的方法是经过优化的回溯法,这个方法其实有些类似于动态规划,但是每一步的决策基本都会影响下一步所以并没有解决重叠子问题而是消除了"无用(不可能)子问题"。当然,这样的话仍然存在真正的重叠子问题,即几块完全不邻接的未翻开格,这时可以先进行划分然后采用分治的思想求解,把计算量从n*m降为n+m。但本项目目前只维护了9*9版本的扫雷,所以划分开销可能比计算量的减少还高故没有实现。
- 以下分析仅以9*9 共81格中10雷的情况进行分析,其他状况同理。
- 从布雷开始,所有情况的可能性都是相等的,显然是一个典型的古典概型,共有C(81,10)种情况。
- 每步点击后,可以排除一部分不符合情况,剩余情况仍然是等概率的。
- 将所有未翻开格划分为活跃与非活跃两部分,活跃即是周围有数字的,非活跃反之。
- 活跃部分的可能情况为所有的可能解,非活跃部分的可能情况要与活跃的雷数对应,假设非活跃有m格,场上剩余雷数为n,活跃的当前解的雷数为k,那么非活跃的可能情况则有C(m,n-k)种。
- 由以上分析可知,首先要根据雷数将可能解划分,然后计算出所有不与规则矛盾的可能情况,这些情况是等可能的,也就是样本空间。
- 对活跃部分来说,它是雷的概率=可能情况中他是雷的情况数/所有情况
- 对非活跃部分来说,它是雷的概率=所有可能情况中非活跃的雷数和/(所有情况*非活跃格数)
- 洗牌算法
将格子的指针存入一维数组,将前x格标为雷,遍历数组,将每一格与本身与他后面的随机一格交换状态,即完成了x个雷的布雷。复杂度O(n)。 - 简单标雷
为了实现上述逻辑,首先需要遍历所有格子,找到所有的数字格,然后需要维护一个"活跃数字格"链表,重复遍历整个链表按照上述逻辑标雷,动态删去已经不活跃的格子并且记录一次遍历中是否有无标记操作操作,直到一轮遍历中没有进行任何标记操作停止遍历。 - 经过优化的回溯法
由于需要假设未翻开格的状态进行推断,这次需要遍历的是一个"活跃未翻开格"链表,同时每步需要动态地维护当前的状态下的"活跃数字格"。
每步假设操作都是把当前处理的格子先标记为雷,然后进行简单标雷操作并校验是否存在不符合规则的项,若有则回撤直接将其假设为无雷继续。假设及推断符合规则的情况相下,若此时"活跃未翻开格"中仍有不确定的格,则对找到的第一格不确定格进行相同的操作。若此时所以"活跃未翻开格"的状态都已经确定,则记录当前结果并返回。然后取消之前的所有操作,再将当前格假设为非雷,重复以上操作。
对"活跃未翻开格"链表的第一格进行上述递归操作,即可获取所有可能解。 - 概率计算:
首先遍历可能解,找到所有解中状态一样的格(全是雷或非雷),将其删去。然后按照上述概率分析部分的思路,计算并存储所有需要的数据,带入公式即可。