2025新年已至,自己用C++实现了一个简单的扫雷AI,功能是对任意给定的局面,判断出尽可能多的格子的状态(有雷或者无雷).当确定某个格子无雷时,由布雷器返回该格子里的数字,然后继续猜测,直到所有可猜的格子都被翻开为止.
下面是一个简单的例子.比如设地雷的实际分布图如下所示:E为非雷格,X为地雷格.整个地图大小为10*10,有10个地雷
1 2 3 4 5 6 7 8 9 10
1 | E | E | E | E | E | E | E | E | E | E |
2 | E | E | E | E | X | E | E | X | E | E |
3 | E | E | E | X | E | E | E | E | E | E |
4 | E | E | E | E | E | E | E | X | X | X |
5 | E | E | E | E | E | E | E | E | E | E |
6 | E | E | X | E | E | E | E | E | E | E |
7 | E | E | E | E | E | E | E | E | E | E |
8 | E | E | E | E | X | E | E | E | E | E |
9 | E | E | X | E | E | E | E | E | E | E |
10 | E | X | E | E | E | E | E | E | E | E |要得到的答案为
1 2 3 4 5 6 7 8 9 10
1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
2 | 0 | 0 | 1 | 2 | X | 1 | 1 | X | 1 | 0 |
3 | 0 | 0 | 1 | X | 2 | 1 | 2 | 3 | 4 | 2 |
4 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | X | X | X |
5 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 2 | 3 | 2 |
6 | 0 | 1 | X | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 0 | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 |
8 | 0 | 1 | 1 | 2 | X | 1 | 0 | 0 | 0 | 0 |
9 | 1 | 2 | X | 2 | 1 | 1 | 0 | 0 | 0 | 0 |
10 | 1 | X | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |程序运行时,首先布雷器只告诉位置(9,9)处的数字为0,然后扫雷器可以自动算出其他格子的状态.
自动扫雷用到的推理规则如下.这里设已经知道某个格子为安全格,且周围有n个地雷
(1)如果n=0则周围的8个格一定都是安全格,则自动翻开这8个格子,得到它们对应的数值,然后继续推理
(2)若已经知道某个格子P为安全格,设Q为P的一个邻居(P周围的8个格子之一),则此时Q周围的已知安全格又多了一个,如果此时Q周围的已知格均确定为安全格,且剩余格的数目等于Q的数字,那么Q的剩余格一定都是雷,然后继续推理
(3)若已经知道某个格子P为安全格,设Q(数字为n)为P的一个邻居则此时Q周围的已知雷又多了一个,如果此时Q周围的已知地雷数等于n那么Q的剩余格一定都是安全格,然后继续推理
(4)减法规则,设P和Q为已知的两个安全格且它们有公共邻居,(此时P和Q可能直接相邻也可能中间隔一行或者一列),那么，对区域P-Q和Q-P,这两个区域的地雷数目的差一定等于P和Q的数字之差.这里P-Q类似于表示集合的差运算,即从第一个集合(P的所有邻居)中去掉所有属于第2个集合(Q的所有邻居)的元素,且还要去掉元素Q本身.
证明如下: 用符号S(P)表示格子P周围的地雷集合,C(P,Q)表示P和Q的公共邻居.
设P和Q互为邻居,则P周围的地雷由如下三部分组成：P-Q中的地雷,公共部分的地雷,以及格子Q本身的地雷(因为Q为安全格,故为0)
即S(P)=S(P-Q)+C(P,Q)+0,
类似的S(Q)=S(Q-P)+C(P,Q)+0
于是可得S(P)-S(Q) = S(P-Q)-S(Q-P)
当P和Q中间隔了一行或者一列时,证法类似.
现在对两个区域(P-Q)和(Q-P)
符号b1,s1,u1分别表示第一个区域的已知地雷数,已知安全格数,未知格的数目
符号b2,s2,u2分别表示第二个区域的已知地雷数,已知安全格数,未知格的数目
又知道S(Q)-S(P)=d>=0.则可得下面两条推理规则
(5)若u1=0,即第一个区域的信息均为已知时,若还知道d==b2-b1,即地雷差的约束已经得到满足,则此时区域2的剩余格一定全是安全格.
(6)若u1=0且b2==0,u2==d,即区域2的已知格全是安全格,而未知格的数目等于地雷差,则此时区域2的剩余格一定都是雷.
对u2=0的情况类似.
