效果
閑來無事，打開虛拟機上的掃雷玩了玩，覺得自己計算很浪費時間，還容易遺漏，就做了個自動掃雷。
簡單模式下很容易通關，困難的就看臉了，感興趣的可以拿去運作一下。
自動化處理核心代碼段在 168~273行。
私信小編01即可擷取大量python學習資源
次日，發現自動掃雷算法并不完整，上次的代碼僅對單個數字周圍進行判斷。
但在一些情況下，單個數字無法判斷，要綜合一片小區域确定某些方塊是否一定是炸彈，或者一定安全。
暫且稱為進階算法。（并不是算法有多進階，本質上還是取集合(區域)，進行大量的判斷，難在複雜判斷的邏輯關系以及集合、字典的操作上）。
通過半天的歸納總結，找到規律後開始設計代碼。
**本次修改還優化了輸出格式，使得在大區域下更容易确定方塊的坐标。**
- 【代碼中一些重複的地方可以提取出來作為單獨的方法，通過改變參數位置來實作相同的功能，讓代碼看上去更精簡】
- 【但長時間的修改代碼，随着變量、變量類型、資料結構嵌套和邏輯關系的不斷增加，有點被搞得頭暈了】
- 【是以既然運作上沒有錯誤，多次試驗也沒有發現毛病，就不去管它了。說不定也是靠着什麼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
這裡我們可以通過【行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
在這裡插入掃雷清單，是因為點開【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) 