本帖最后由 大脑组织残缺 于 2021-10-28 12:22 编辑
闲来无事，打开虚拟机上的扫雷玩了玩，觉得自己计算很浪费时间，还容易遗漏，就做了个自动扫雷。
简单模式下很容易通关，困难的就看脸了，感兴趣的可以拿去运行一下。
自动化处理核心代码段在 168~273行。
========================
次日，发现自动扫雷算法并不完整，上次的代码仅对单个数字周围进行判断。
但在一些情况下，单个数字无法判断，要综合一片小区域确定某些方块是否一定是炸弹，或者一定安全。
暂且称为高级算法。（并不是算法有多高级，本质上还是取集合(区域)，进行大量的判断，难在复杂判断的逻辑关系以及集合、字典的操作上）。
通过半天的归纳总结，找到规律后开始设计代码。
**本次修改还优化了输出格式，使得在大区域下更容易确定方块的坐标。**
【代码中一些重复的地方可以提取出来作为单独的方法，通过改变参数位置来实现相同的功能，让代码看上去更精简】
【但长时间的修改代码，随着变量、变量类型、数据结构嵌套和逻辑关系的不断增加，有点被搞得头晕了】
【所以既然运行上没有错误，多次试验也没有发现毛病，就不去管它了。说不定也是靠着什么bug运行起来了呢】
【事实上最初写出来的高级算法代码还多了一个子模块，这个模块在一次高级算法结束之后进行进一步处理】
【在设计算法的时候，考虑到这样能减少遍历游戏窗口的次数，加快运行速度，并且可以确定更多的更复杂的坐标及操作】
【虽然写好代码之后第一次运行全自动困难模式顺利通关，但在后来的几次测试中总会错把炸弹点开😭】
【而且计算出的坐标我实在是看不懂根据什么条件算出来的，修改多次无果，想着是不是算法最初处理的时候就是错误的】
【把这段代码注释掉之后，多次测试，没有任何错误，而且计算出来的坐标和操作都是正确的！计算不出来的时候，我看着也是无法确定哪个方块安全】
【这种情况下只能靠运气随机选择。所以上文说到，说不定是靠着什么bug运行起来的呢。】
========================
教学时间：
咱都上榜一了，咋能不出个教学呢。
（绿色底为算法讲解，蓝色底为举例说明，无色底、算是旁白或设计算法的过程吧。）
首先介绍下扫雷的冷知识：
扫雷上面数字的意思是该方块周围八格方块中的雷的个数。
有时候点一下会开一大片。是因为点到了数字0。0周围没有方块，游戏会自动向四周扩散，直到有数字的方块停止。（0向四周扩散是不可能遇到雷的）
这段“点到0向四周扩散”的代码在141~150行，通过126-128行进入。通过非常简单的递归实现的，遍历一遍0方块周围的方块，是数字就显示数字，是0就再次调用该方法，传入该位置。这段代码可以优化，但重点是自动扫雷。
生成一局扫雷的方法：（对应代码43 ~ 63行）
先生成指定大小（m×n）的空间。我在这里用了二维数组表示，初始化全为0，程序中变量名为game_space， 然后随机k(k个雷)个不同坐标，用’*‘表示雷，记录在数组中。
然后遍历一下每个雷的周围八个格子，如果不是字符’*‘，则+1。生成完成。（可以验证，数字与周围雷的数量都是匹配的）
可能有同学会质疑，既然game_space列表已经记录了雷的位置，那还有啥扫的？
实际上，扫雷游戏就是提前生成好的游戏棋盘数据，然后在每个格子上都盖上盖子而已。这里表示顶层盖子的列表是show_list。
所有的操作都在show_list列表上，game_space列表仅用于点击show_list列表时进行数据补充。相当于掀开了外层的盖子，露出了里面的内容。
自动扫雷：
自动扫雷就是一个模拟玩家扫雷的过程。你开一局扫雷，第一个肯定是要随便点的。如果运气爆棚，是可以直接点到雷结束该局游戏的。
点到数字一般也不会是8。一般都是从点到0开始才能判断哪里是雷，哪里是安全的。
这里开一局“简单”模式的扫雷，8*8大小，10个雷。用于举例说明。（顺带一提，我写的输出格式在pycharm里输出是整齐的。没有在IDLE里测试过。这里粘贴过来■就比数字宽些）
随机选择【4, 3】点开
Game Over!
1│ ■ ■ ■ ■ ■ ■ ■ ■
2│ ■ ■ ■ ■ ■ ■ ■ ■
3│ ■ ■ ■ ■ ■ ■ ■ ■
4│ ■ ■ * ■ ■ ■ ■ ■
5│ ■ ■ ■ ■ ■ ■ ■ ■
6│ ■ ■ ■ ■ ■ ■ ■ ■
7│ ■ ■ ■ ■ ■ ■ ■ ■
8│ ■ ■ ■ ■ ■ ■ ■ ■
运气爆棚，一发入魂。 再开一局。
再开N局。
无法确定位置，随机选择【2, 1】点开
无法确定位置，随机选择【4, 8】点开
1│ ■ ■ ■ ■ ■ ■ 1 0
2│ 1 ■ ■ ■ ■ ■ 1 0
3│ ■ ■ ■ ■ ■ 1 1 0
4│ ■ ■ ■ ■ ■ 1 0 0
5│ ■ ■ ■ ■ ■ 3 1 1
6│ ■ ■ ■ ■ ■ ■ ■ ■
7│ ■ ■ ■ ■ ■ ■ ■ ■
8│ ■ ■ ■ ■ ■ ■ ■ ■
这里我们可以通过【行3列7】（以下使用形如【3，7】表示）确定【2，6】是雷，因为【3，7】周围只有【2，6】没有点开，而【3，7】周围只有一个雷。
给【2，6】插上旗子之后，又可以通过【1，7】判断【1，6】是安全的，可以点开；可以通过【3，6】判断【2，5】【3，5】【4，5】是安全的。
【2，5】【3，5】【4，5】点开后 又可以通过【4，6】判断【5，5】是雷。
自动算法说明：（该段代码在174-198行）。
扫雷棋盘使用二维数组表示，首先通过两层循环遍历，找到一个大于0的数字，使用一个变量’z‘记录这个数字。
再遍历一下该数字周围的八格格子，这里我又使用了两层循环实现。（代码在178-180行，要确保坐标不超界）。
在遍历过程中，若发现插了旗子‘□’的格子，则让z - 1，表示z周围已经确定了1个雷，所以还剩z - 1个雷。
如果发现了还没有点开过的格子’■‘，则记录该坐标。（代码中用类变量coordinate_list列表记录）
八个格子遍历完成后，若 z 等于 0， 则说明coordinate_list列表中记录的’■‘格子都是安全的，可以点击，于是将coordinate_list列表中的每个坐标后记录可以点击（即操作1），返回。
若z 等于 coordinate_list列表的长度，则可以确定coordinate_list列表中记录的’■‘格子都是雷 ，给这些坐标记录上插旗操作（即操作0），返回。
剩下的情况就是coordinate_list列表长度 大于 z了，这种情况无法确定记录的格子是什么东西，则清空coordinate_list列表， 继续循环，寻找下个数字进行这套操作。
注意到z = 0时，coordinate_list列表可能为空，所以要在返回前判断coordinate_list列表非空。（代码194行）
返回的只是列表中的一个坐标及操作，若列表中有多个坐标，要全部进行相应操作。对应代码（168-172行）
（这段代码）
还可以通过综合一个区域判断【6，5】【6，7】一定是雷，因为【5，6】周围有3个雷，【5，5】是1个，剩下两个在【6，5】【6，6】【6，7】中；
而通过【5，7】可知【6，6】【6，7】【6，8】中只有1个雷，所以【6，5】一定是雷。又由【5，8】可知【6，7】【6，8】中有1个雷，
所以【6，7】一定是雷，【6，6】【6，8】安全。若存在疑惑，可通过假设法假设【6，6】或【6，8】是雷，通过推导出雷周围的数字与数字周围的雷数不符合，得到验证。
这里就是上面提到的“高级算法”，会在下文中详细介绍算法（就是一堆复杂的数据结构和逻辑判断）。
这里只是说明了通过现在的局面可以判断到的格子，在自动扫雷程序中是按行先遍历的，不一定就是按我说的这些去依次点开，可能点开【1，6】后又能判断出【1，6】周围的格子是安全的了。
（顺带一提，有🚩图文字，但是宽度和方块、数字不一样，为了输出排版，就换成了白色方块□ 代替🚩。大家也可以修改代码，将所有字符、数字换成全角。）
让我们继续游戏：（操作0是插旗的意思，操作1是点开的意思）
选定位置【2, 6】, 操作为：0
选定位置【1, 6】, 操作为：1
1│ ■ ■ ■ ■ ■ 1 1 0
2│ 1 ■ ■ ■ ■ □ 1 0
3│ ■ ■ ■ ■ ■ 1 1 0
4│ ■ ■ ■ ■ ■ 1 0 0
5│ ■ ■ ■ ■ ■ 3 1 1
6│ ■ ■ ■ ■ ■ ■ ■ ■
7│ ■ ■ ■ ■ ■ ■ ■ ■
8│ ■ ■ ■ ■ ■ ■ ■ ■
在这里插入扫雷列表，是因为点开【1，6】后可通过【1，6】【2，6】判断【1，5】【2，5】安全，已经和我上面所述的操作路径不同了。
下面我不在详细展示，让我们直接快进到需要重要介绍的位置。
选定位置【2, 5】, 操作为：1
选定位置【1, 5】, 操作为：1
……
……
1│ 0 0 1 □ 2 1 1 0
2│ 1 1 2 1 2 □ 1 0
3│ 2 □ 2 0 1 1 1 0
4│ 2 □ 2 1 1 1 0 0
5│ 2 2 1 2 □ 3 1 1
6│ □ 1 0 3 □ ■ ■ ■
7│ 2 2 1 2 □ 3 1 1
8│ 1 □ 1 1 1 1 0 0
调用高级计算处理，请等候...
计算完成!生成操作:
坐标【6，8】，操作：1
坐标【6，6】，操作：1
========================
选定位置【6, 6】, 操作为：1
选定位置【6, 8】, 操作为：1
选定位置【6, 7】, 操作为：0
可以看到，通过上面简单的计算，已经快将游戏解完了。在简单模式下，多数情况根本用不上高级计算，这局游戏是开了许多局才调用到了高级算法代码，就算没有高级算法，也可以通过随机方法随机一个坐标点开，有2/3的概率是数字，只要点开一个是数字，就可以确定最后一个雷的位置了。
可由【5，8】知道【6，7】【6，8】中有1个雷，由【5，7】知道 【6，6】【6，7】【6，8】中有1个雷，所以【6，6】一定是安全的，可以点开。
可由【5，6】得知【6，6】【6，7】中有1个雷，综合【5，7】，可以确定【6，8】是安全的，可以点开。
这就是需要通过综合一片区域才能确定的，用代码实现确实比较复杂。
高级算法说明：（代码在228~273行，通过202行调用）
要将这种思想转化为代码，就要先总结他们共有的特征，就是找规律。规律是：求差集。
这里要用到python的 字典、集合、元组、列表。
首先，我将游戏输出列表show_list做了一个处理，把所有>0的数字减去他们周围已经插旗的个数，结果保存在了processed_list列表中。（代码229~247行）
在处理之前 要先创建一个空的集合c（代码238行），在遍历数字周围八个方格时，如果遇到没有打开的方格’■‘，则在c中记录该方格坐标。这里，我们相当于得到了一个区域。
遍历完八个方格之后，如果集合c非空，那么处理的数字一定还>0，将集合c转变为元组，作为字典的键，处理后的数字做为该键对应的值。（字典名为set_dic）
对上面的示例，该操作能得到：
1│ 0 0 0 □ 0 0 0 0
2│ 0 0 0 0 0 □ 0 0
3│ 0 □ 0 0 0 0 0 0
4│ 0 □ 0 0 0 0 0 0
5│ 0 0 0 0 □ 1 1 1
6│ □ 0 0 0 □ ■ ■ ■
7│ 0 0 0 0 □ 1 1 1
8│ 0 □ 0 0 0 0 0 0
并得到字典set_dic = {((6, 6), (6, 7)) : 1, ((6, 6), (6, 7), (6, 8)) : 1, ((6, 7), (6, 8)) : 1} 【解释下为什么要将集合c转化为元组，因为集合是可变数据类型，属于非可哈希类型，无法作为字典的键。】
之后就是对字典的两层循环：取其中一个键，（取完键之后首先转变为集合类型，通过集合类型自带的判断子集的方法），与其他键做判断是否为子集。
如果是子集，即可求差集，并求这两个键对应值的差。如果值的差为0，说名求得的差集中的坐标是安全的，可以打开；如果值的差非零，如果值得差等于差集的长度，说明差集中的坐标一定是雷，需要插旗。（代码249~273）
对应上面的示例，集合a = {(6, 6), (6, 7)} 是 集合b = {(6, 6), (6, 7), (6, 8)}的子集， 求差集 b - a 得到差集{(6, 8)}, 差值为0，说明坐标（6，8）的方格’■‘是安全的。
之后就是将元组（6，8）转换为列表[6, 8]，加入操作码得到[6, 8, 1]，加入到操作列表 coordinate_list 中。
讲解结束。这也不算难，也得益于python本身的优势。如果用其他语言，还要定义大量结构体，或无休止的取值赋值。
这里顺便说个bug，代码中在得到差集和差值后，加入操作列表的时候没有判断要插入的数据是否已经存在。因为可能通过不同的集合判断得到同一个差集，如果是点击操作还好，点击过后该方块不能再进行其他操作，但如果是插旗，那么插旗之后再插旗就是取消插旗。
而操作完成之后，下次高级判断可能还会得到两次相同坐标的插旗操作，那么程序将进入无线循环。所以可以将 coordinate_list 列表变成集合类型，集合本身不允许重复，或者在向 coordinate_list 列表加入数据前前进行一个重复判断。
这个bug是在测试 行100，列200，雷3000的游戏中发现的bug。小规模一般不会遇到。
==========================
【可以将带有注释的time.sleep代码给打开，在括号内设置合适的时长，可以看到自动扫雷的过程】
代码【】
[Python] 纯文本查看 复制代码 import random
import time
class SaoLei:
m: int
n: int
k: int
mode: int
coordinate_list = []
game_space: list[list[int or str]]
def __init__(self, m: int, n: int, k: int, mode: int):
"""
初始化游戏
:param m: m行, m >= 8
:param n: n列, n >= 8
:param k: k个雷, 10 <= k <= m*n*0.3
:param mode: 0：手动模式，1：全自动模式 2：半自动模式
"""
if m >= 8:
self.m = m
else:
print("row Error!")
exit(0)
if n >= 8:
self.n = n
else:
print("col Error!")
exit(0)
if 10 <= k <= m * n * 0.3:
self.k = k
self.flag = self.k
else:
print("k Error!")
exit(0)
if mode in (0, 1, 2):
self.mode = mode
else:
print("Mode Error!")
exit(0)
# 生成区域
self.game_space = [[0 for _ in range(n)] for _ in range(m)]
print("game_space create success!")
# 随机雷的位置
i = 0
while i < self.k:
a = random.randint(0, m - 1)
b = random.randint(0, n - 1)
if self.game_space[a][b] != '*':
i += 1
# 产生数据
self.game_space[a][b] = '*'
c = [-1, 0, 1]
for x in c:
if 0 <= a + x < m:
for y in c:
if 0 <= b + y < n:
if self.game_space[a + x][b + y] != '*':
self.game_space[a + x][b + y] += 1
# 调用游戏进程
self.game_window()
def game_window(self):
show_list = [['■' for _ in range(self.n)] for _ in range(self.m)]
text = ''
while True:
# 输出画面
for i in range(10):
print()
print(text)
print("+++" * self.n, end='+\n')
print(' │ ', end='')
for k in range(1, self.n + 1):
print('%d' % (k % 10), end=' ')
print('\n─┼─', end='')
print('───' * (self.n - 1), end='─\n')
k = 1
for i in range(self.m):
print(k, end='│ ')
for j in range(self.n):
print(show_list[i][j], end=' ')
print()
k = (k + 1) % 10
if text == 'Game Over!':
exit(0)
text = ''
# 检测是否结束
row = self.m
for i in show_list:
if '■' not in i:
row -= 1
if row == 0:
print('Victory!')
exit(1)
# 输入坐标及操作
if self.mode == 0:
a, b, c = self.input_set()
else:
a, b, c = self.automatic_input(show_list)
# 进行处理
if c == 0:
if self.flag > 0:
if show_list[a][b] == '■':
show_list[a][b] = '□'
self.flag -= 1
elif show_list[a][b] == '□':
show_list[a][b] = '■'
self.flag += 1
else:
text = 'Error! Is number'
else:
text = 'Error! No flag'
elif c == 1:
if show_list[a][b] == '■':
if self.game_space[a][b] == '*':
show_list[a][b] = '*'
text = 'Game Over!'
elif self.game_space[a][b] == 0:
show_list[a][b] = self.game_space[a][b]
self.look_zero(a, b, show_list)
else:
show_list[a][b] = self.game_space[a][b]
else:
text = 'Error! No Click'
elif c == 2:
if show_list[a][b] == '■':
show_list[a][b] = '?'
elif show_list[a][b] == '?':
show_list[a][b] = '■'
else:
text = 'Error! Open'
def look_zero(self, a: int, b: int, show_list):
for i in range(a - 1, a + 2):
for j in range(b - 1, b + 2):
if 0 <= i < self.m and 0 <= j < self.n:
if show_list[i][j] == '■':
if self.game_space[i][j] == 0:
show_list[i][j] = 0
self.look_zero(i, j, show_list)
else:
show_list[i][j] = self.game_space[i][j]
def input_set(self):
a = int(input("输入行："))
b = int(input("输入列："))
c = int(input("操作（0：插旗； 1：点击； 2：标记）："))
if not (0 < a <= self.m and 0 < b <= self.n and c in (0, 1, 2)):
a, b, c = self.input_set()
a += 1
b += 1
return a - 1, b - 1, c
def automatic_input(self, show_list: list[list]
):
"""
自动化方法
:param show_list:
:return:a,b,c
"""
if self.coordinate_list:
a = self.coordinate_list.pop()
print("选定位置【%d, %d】, 操作为：%d" % (a[0] + 1, a[1] + 1, a[2]))
# time.sleep(0.5)
return a[0], a[1], a[2]
for i in range(self.m):
for j in range(self.n):
if type(show_list[i][j]) is not str and show_list[i][j] > 0:
z = show_list[i][j]
for x in range(i - 1, i + 2):
for y in range(j - 1, j + 2):
if 0 <= x < self.m and 0 <= y < self.n:
if show_list[x][y] == '□':
z -= 1
elif show_list[x][y] == '■':
self.coordinate_list.append([x, y])
if z == 0:
for p in range(len(self.coordinate_list)):
self.coordinate_list[p].append(1)
elif z == len(self.coordinate_list):
for p in range(len(self.coordinate_list)):
self.coordinate_list[p].append(0)
else:
self.coordinate_list.clear()
if self.coordinate_list:
a = self.coordinate_list.pop()
print("选定位置【%d, %d】, 操作为：%d" % (a[0] + 1, a[1] + 1, a[2]))
# time.sleep(0.5)
return a[0], a[1], a[2]
# 进入高级计算
print("调用高级计算处理，请等候...")
self.advanced_automatic_input(show_list)
if self.coordinate_list:
print("计算完成!生成操作:")
for mmm in self.coordinate_list:
print("\t坐标【%d，%d】，操作：%d" % (mmm[0] + 1, mmm[1] + 1, mmm[2]))
print("========================")
a = self.coordinate_list.pop()
print("选定位置【%d, %d】, 操作为：%d" % (a[0] + 1, a[1] + 1, a[2]))
# time.sleep(0.5)
return a[0], a[1], a[2]
# 无法确定，随机选择位置
elif self.mode == 1:
a = random.randint(0, self.m - 1)
b = random.randint(0, self.n - 1)
while show_list[a][b] != '■':
a = random.randint(0, self.m - 1)
b = random.randint(0, self.n - 1)
else:
print("无法确定位置，随机选择【%d, %d】点开" % (a + 1, b + 1))
# time.sleep(2)
return a, b, 1
else:
print("无法确定位置，请手动输入。 提示：还有【%d】个💣" % self.flag)
return self.input_set()
def advanced_automatic_input(self, show_list: list[list]
):
processed_list = []
set_dic = dict()
for i in show_list:
processed_list.append(i.copy())
# 初步处理
for i in range(self.m):
for j in range(self.n):
if type(processed_list[i][j]) is int and processed_list[i][j] > 0:
c = set()
for p in range(i - 1, i + 2):
for q in range(j - 1, j + 2):
if 0 <= p < self.m and 0 <= q < self.n:
if processed_list[p][q] == '□':
processed_list[i][j] -= 1
elif processed_list[p][q] == '■':
c.add((p, q))
if c:
set_dic[tuple(c)] = processed_list[i][j]
# 寻找子集
key_list = list(set_dic.keys())
for i in range(len(key_list)):
for j in range(i + 1, len(key_list)):
if len(key_list[i]) < len(key_list[j]):
p = i
q = j
elif len(key_list[i]) > len(key_list[j]):
p = j
q = i
else:
continue
if set(key_list[p]).issubset(set(key_list[q])):
d = list(set(key_list[q]) - set(key_list[p]))
if set_dic[key_list[q]] - set_dic[key_list[p]] == 0:
for k in d:
e = list(k)
e.append(1)
self.coordinate_list.append(e)
elif set_dic[key_list[q]] - set_dic[key_list[p]] == len(d):
for k in d:
e = list(k)
e.append(0)
self.coordinate_list.append(e)
# 传参【 m行，n列， k个雷， mode：0、手动； 1、全自动; 2、半自动】，可自定义
# 简单 8 8 10
# 一般 16 16 40
# 困难 16 32 99
game = SaoLei(16, 32, 99, 2)
排版、半自动模式展示
新加入的“高级算法”
无法确定的情况，全自动模式会随机选择方块点开，半自动模式在该情况下是手动输入坐标及操作。
胜利展示
|
[复制链接]
发表于 2021-10-23 20:19
|
发表于 2022-11-13 18:38
