必须使用剩余雷判定时是否一定是最后一步
昨天 21:4640 浏览综合
完整标题:无猜扫雷中必须使用剩余雷判定是否一定是最后一步?
假设我们使用数字一直推理然后彻底推理不出来了,那么说明此时必须使用剩余雷判定,这个时候是不是最后一步,如果不是,有没有反例局面可以给出?
这是我给出的证明:
0.设当前所有未打开的格子为集合S。
1.假设剩余雷判定不是最后一步。
2.那么它只能确定部分剩余格子的情况,设其能够确定的格子集合为S1,不能够确定的格子集合为S2,此时S1+S2=S。
3.我们知道,扫雷可以分割成多个不同的未打开的区域,它们在不考虑剩余雷的情况下是相互独立的。如果考虑剩余雷,假设有n个区域,分别为A1、A2……An。通过数字限制的某个区域Ai的最大雷数为Aimax,最小雷数为Aimin。我们可以使用剩余雷判定所有区域的精确雷数的必要条件为满足以下条件中的任意一个:
A. 所有区域Aimin之和等于剩余雷数
B. 所有区域Aimax之和等于剩余雷数
C. 只有一个区域
而剩余雷判定除了可以瞬间知道所有区域的精确雷数之外毫无用处,实际上根据精确雷数和这个区域的数字才有可能推理出唯一解,这个时候一整个区域就被解决了。
4.那么S2中必定包含所有知道精确雷数但无法确定具体状态的Aa,S1中必定包含所有可以确定状态的Ab,那么我们打开了所有Ab,但是由于Aa与Ab之间互相独立,打开了Ab不会提供任何信息给Aa,且我们的前提是已经无法通过数字推理了,那么Aa将永远无法求解,这与我们的前提无猜局面矛盾。
5.假设不成立,证毕!
证明是否正确呢?![[表情_微笑]](https://img.tapimg.com/market/images/0f170d4b1ecf80c267e5a44b5992a199.png)
![[表情_微笑]](https://img.tapimg.com/market/images/0f170d4b1ecf80c267e5a44b5992a199.png)