玩掃雷還有什麼技巧？科學家的玩遊戲方法你絕對想不到

掃雷標雷的快捷鍵是什麼

有時，小編回憶起童年和青春，眼前總是浮現出一片

碧藍碧藍的天空

和

嫩得出水的草地

，以及以前在那上面和小夥伴們度過的愉快的時光……

當然，你們別想錯了

我說的藍天和草地是指這個

為了防止被打小編選擇提前爆頭蹲防

Windows XP 確實承載很多的記憶，而且 XP 這個系統也是真的經用。Windows XP 於 2001 年 8 月 24 日正式釋出，微軟在

2014 年 4 月 8 日

才停止了對 Windows XP 桌面版系統的支援服務，一直到這週二，

2019 年 4 月 9 號

，執行在嵌入式裝置上的最後的一批 Windows XP 才失去微軟的官方支援。XP 們終於正式對我們 say goodbye 了。［1］

經典的掃雷遊戲

提起 XP，不得不說作業系統自帶的諸如

掃雷

，

紙牌

這一類的經典遊戲真的經典，好玩又殺時間。如果可以統計全人類花在這上面的時間，估計肯定是一個天文數字。。。不過儘管掃雷大家玩的時間很長，玩的次數也很多，但是我猜 99% 的玩家肯定沒思考過，自己玩掃雷為啥那麼容易就死了。。。

對比一下

別人家的孩子玩掃雷的速度

圖片經過加速。如果你想看真正目前世界上掃雷最快的記錄的話，可以去 ［2］ 圍觀

再看看

自己玩掃雷的樣子...

差不多就是這種水平，剛點到掃雷圖示雷就已經炸了

雖然 XP 已經離我們而去，但是萬幸的是 Win10 系統還能夠在商店中直接

搜尋

「minesweeper」

下載

官方重置了的掃雷遊戲，重新體會以前的經典。

其實吧，掃雷這個遊戲很多科學家也愛玩。不過一般人玩掃雷如果死得快，就

不斷重開重開重開

直到碰到一個好的開局（然後又快速地死掉）。科學家就不一樣，如果他們玩掃雷死得快，他們不會重開，他們會

直接證明「這個遊戲通關機率為 0」

。

掃雷畢竟已經有這麼長的歷史了，分析掃雷遊戲求解機率的論文都有一大堆。

作為一個熟練點選掃雷重開鍵的手殘掃雷玩家

，今天我就來和大家系統地聊一聊掃雷的背後的故事。

掃雷秘籍

Minesweeping cheat sheet

天下武功，無堅不摧，唯

快

不破！

從數學上來看，掃雷就相當於一個不斷給你已知條件不斷求解的過程，就像一個不斷增加條件的應用題。你可以透過

左鍵點開

確定不是雷的塊，

右鍵標記

你認為是雷的區域。如果你點開的這一塊不是雷，那麼它會告訴你這塊區域周圍八格內有幾顆雷。只要你點得足夠快，雷就追不上你。

透過很簡單的反證法，我們可以推出來很大一部分雷所在的位置。［3］

角落上的情形

所謂反證法，就是反過來想這個問題。如果存在這麼一個向內凹的角，內部的都是空白，但是角落上是一個 1，那麼這個角上一定會有一顆雷。因為如果這個地方再不是雷的話，那中間的 1 所指的雷就只能去流浪了。。。同理，一條邊上如果有 3 的話，那和 3 挨著的這三個一定是雷。畢竟地雷兄弟們也不能擠一擠挪到一個格子上去。

位於邊界時候的情形

除了這個反證法以外，在掃雷裡還有很多固定的

「套路」

。學會這個套路，保證你掃雷功力大增，殺進小區掃雷五百強。

聽起來好像很厲害的樣子

在掃雷的時候其實經常會遇到一些固定的數字，比如三個連續的數字為

121

，此時想都不用想，就可以直接在

121 兩個 1 的正對方向標上雷

。或者四個連續的數字

1221

，此時

兩個 2 的正對方向上也一定是雷

。

121 情形下，由於左側 1 的限制，在黃色區域內只能有一格雷，但是中間的 2 至少要求 2 格雷，所以粉色的那顆一定是雷。同理證明另外一側

1221 情形下，和上面證明過程相同，由於 1 的限制導致在黃色區域內只能有 1 格雷，所以另一個 2 正對的方格一定是雷。

「小編小編，我有個問題，那 121221 呢？按照秘籍填雷的話中間那個 1 附近有兩顆雷誒？」

似乎有問題的秘籍？

「這種情況是不可能的！左邊數起三個 1 已經覆蓋了上面的所有未知空格，所以地雷數至多隻有 3 個。但下方顯示地雷數為 1+2+2+1+2+1，在只有中間 5 個格子重複計數的情況下都到了 7，大於 3 的 2 倍。所以這種圖形是不可能存在的！」

咳咳，把思路收回來，如上所述，

掃雷確實是有一些套路的

。每日熟讀此掃雷秘籍，假以時日，掃雷技藝必將大成。

掃雷還是運氣活

Lucky or not，it‘s a question

玩掃雷，你必須要接受，這是一款

拼人品

的遊戲。

雖然人生已經如此地艱難，但我還是要無情地拆穿這一點。想必你此時已經熟練掌握了掃雷的套路，不過在有些時候你還是要面對

猜雷

這種事情，而且一招不慎，滿盤皆輸。。。

猜猜黃色部分的雷應該是怎麼分佈的？

圖中黃色部分就是典型的需要猜的掃雷難題。根據角落裡面的數字，我們都

只能知道 1×2 的黃色部分裡面一定只有一個雷

，不過我們並不知道哪個才是雷。如果沒有其它資訊的話，我們辛辛苦苦大半個棋盤，最後透過這個地雷陣的機率還是隻有

1/8

。

這種簡單的判斷還好，有些時候還會遇到一些藏得更加隱晦的猜的時候。

掃雷判斷題

假設在我們的掃雷過程中遇到了這麼一個圖案，確實是一件欲哭無淚的事情。不知道怎麼哭的可以先把眼淚準備好，小編馬上就告訴你們為啥要哭。。。從左邊開始，假設第一個空位有雷，那麼第二個空位沒有雷，因為空位中間 1 的存在從而第三個空位有雷，依次類推。但是如果是第一個空位沒有雷，而第二個空位有雷，我們也說得通。都要踩地雷了，還整個這麼複雜的難題，至於麼。。。

別急，後面還有更加複雜的。這裡的 x 和之後的 * 號上是否有雷的情況一直相同，所以

這個地雷陣就像一根傳遞訊號的導線一樣

。在掃雷的地圖上，

我們不僅僅能夠做出這種簡單的傳遞訊號的導線，其實還能夠實現所有的電子電路中的邏輯閘的操作

。［4，5］

非閘電路

或閘電路

這是兩個「簡單」的邏輯閘，分別實現了

將訊號翻轉的非門

和

將兩路訊號做或操作的或門

。在另一個也很著名的沙盒遊戲——《我的世界（Minecraft）》裡面，玩家也可以透過遊戲中的材料，紅石（其實在此之前的 Windows 10 作業系統的每一年的更新代號就是用紅石來命名），實現各種各樣的複雜邏輯操作，更有玩家利用紅石在 Minecraft 裡製造出了真正能執行的計算機。。。

紅石計算機，具有完整的暫存器，加法器等部件 ［6］

算了，我已經不敢想象掃雷會變成什麼樣了。。。

判斷有沒有解都是一件很難的事情

Find solution

回到文章最開始，我們人去破解一個掃雷問題的話，很容易就會死掉了，那把這個問題交給計算機來做會怎麼樣？

然而很遺憾的是，一般情況下，計算機目前對掃雷這個問題還是無能為力。。。

難過

稍微值得慶幸的是，在我們平時玩的比較小的棋盤下，計算機還可以透過

搜尋

得到答案。

為了瞭解計算機處理問題難度的幾個級別，有必要先知道一個概念——

多項式時間

。

對於同一個演算法，根據處理問題大小的不同，計算機一般來說需要不同的時間進行計算。

用最直觀的例子來說，小明要去洗衣服，他洗 1 件衣服的時間為 2 分鐘，洗 5 件衣服的時間為 10 分鐘，洗 10 件衣服的時間為 20 分鐘，

處理問題的時間隨問題規模的變化為線性關係

，一次多項式。現在我們假設小明還是要洗衣服，只不過現在的衣服比較特殊，他洗 1 件這種衣服的時間為 2 分鐘，但洗 5 件的時間變為 32 分鐘，洗 10 件的時間變為 1024 分鐘，

這個時候就是指數關係的，而不再是多項式了

。評價一個演算法，隨著問題規模的增大，計算時間怎麼增長是一個十分重要的指標。

在計算機裡面，對於多項式級別的時間，我們還是認為很快的。

如果把問題按照求解的難度來進行分類的話，

P

是指能夠用多項式時間求解的問題，俗話說就是

算起來很快

的問題。

NP

是指算起來不一定快，但是任何答案我們都可以

檢查起來很快

的問題。

NP 完全問題，是比所有 NP 問題都要難的 NP 問題。

雖然人們有個美好的想法，總覺得驗算起來很快的應該可以找到辦法讓他算起來很快，但目前還是個未知數。。。［7］

很不幸，

求解一個掃雷遊戲的解，正好是一個 NP 完全問題——在能夠輕鬆驗證結果是否正確的問題裡面最難的那一類。

這一類問題目前為止人們還沒有發現多項式時間的求解演算法，通常只有指數級甚至階乘級的

搜尋

演算法來解決。

用來顯示液晶數字的邏輯電路。我們可以很方便地一個一個試，但是反過來卻很難，尤其是在這個邏輯電路非常龐大的時候

掃雷遊戲屬於一個如此困難的問題，其原因就出在上一章提到的，可以把掃雷遊戲看做一個個邏輯閘進行運算的邏輯電路。給定一個邏輯電路，在已知輸出結果的情況下，能否確定每個輸入的值？這個問題被稱為

SAT 問題，是世界上第一個被證明其為 NP 完全的問題

。［8］這種問題驗證起來非常容易，你只需要把結果代入到邏輯電路中，馬上能知道是否符合要求，但倒過來想要計算符合結果的輸入就極端地麻煩。

求解掃雷遊戲的結果，利用那些構造的邏輯閘，恰恰等價於求解 SAT 問題。［9］

掃雷還和滲透有關係

Precolation

液體，圖片來自 Giphy，Michael Shillingburg

其實我們在玩掃雷遊戲的時候覺得很難，其實還有另外一個原因。這個原因和物理裡面的

滲透

還有關係。

在上個世紀 60 年代，科學家們 ［10］ 發現

在流體流過多孔的介質的時候，介質中的空洞總是會被堵塞，有時候就會影響流體流出。

更為奇怪的是，當這些多孔的介質的孔隙被隨機堵塞的比例逐漸增大而達到某一值時，一開始一直能夠流動的流體就突然被完全堵住。在孔洞被隨機堵住的機率發生變化時，液體流過的比率也會發生一個突變。

這種現象被稱為

逾滲

（precolation）。［11］

遇到這種情況，你該怎麼下手

在掃雷裡面，也存在類似逾滲的現象。

當一盤遊戲裡面的地雷密度特別低的時候，我們差不多隨便點，都不會點到地雷，而是點到大片大片的空白，一下子就把問題解決了。但是當地雷密度增高以後，在增大到一定程度以後，即使我們理性地分析，從不瞎猜，也不可能把掃雷問題做對了。

針對不同的棋盤大小，有人計算了在不同地雷密度情況下獲勝的機率。三角形對應的曲線為初級 8×8，正方形為 15×13，菱形為高階，

30

×16。這裡的能否求解實際上不包括第一次隨機點選的時候踩中雷的機率。［12］

我們把流體透過多孔介質逾滲的模型抽象出來的話，其實對應著點逾滲，也就是把整個介質想象成一個網路，流體在經過每個網格時，有機率 p 的可能透過。

如果不能流過的網格在網路中連成了片，流體就不能流過了。

不嚴格地來說，求解掃雷問題其實和逾滲模型很類似，我們求解的過程其實也像

推土機一樣

，不斷地利用已有的知識將已知區域向外一層一層地推進。如果遊戲中某處雷的密度越大，那麼越有可能出現可解部分被雷分開的情況，

地雷密度和逾滲引數起到了一樣的作用

。如果被分隔到無法連線整個棋盤，那就無法繼續推理了。更為嚴格的證明可以參考 Elchanan Mossel 的論文。［13］

推土機，圖片來自網路

隨著網格的不斷增大，這條勝率曲線中間部分也變得越來越陡峭，掃雷問題越來越向兩個極端發展：

要不就根本解不出來，要不就是很容易地就能解出來。

在高階模式下，地雷的密度其實已經到了 99/480 = 0。2，能夠解出來的機率已經不到 1/4，這還不算手抖了點錯了，開局不好重開之類的情況，真的不算是友好了。

結 論

Conclusion

emoji 版本掃雷 ［14］

相信看到這裡的人

一定已經

躍躍欲試

想要玩一下掃雷了

我相信你們

天下無難事，只要肯放棄

解除安裝也行

* 封面圖修改自周星馳電影《功夫》

* 參考文獻以及連結：

［1］ 最後的 Windows XP 退役

［2］ Minesweeper Game World Ranking

［3］ 更詳細的掃雷教程可以點選閱讀 Strategy - MinesweeperWiki，對更具體的細節感興趣的，可以閱讀掃雷遊戲有些什麼技巧嗎？ - 張砷鎵的回答 - 知乎

［4］ Minesweeper and logical circuits

［5］ 要成為掃雷高手，先練好邏輯吧 - Albert_JIAO，果殼

［6］ Quad-Core Redstone Computer - YouTube

［7］ 什麼是P問題、NP問題和NPC問題，以及怎麼理解 P 問題和 NP 問題？- 知乎

［8］ 布林可滿足性條件 - 維基百科

［9］ Circuits， Minesweeper， and NP Completeness - Richard Carini

［10］ S R Broadbent and J M Hammersly，Percolation processes。 Proceedings of the Cambridge Philosophical，1957，53 ：629-

641

。

［11］ Percolation - wikipedia

［12］ Minesweeper as a Constraint Satisfaction Problem - Chris Studholme

［13］ The Minesweeper game： Percolation and Complexity - Elchanan Mossel

［14］ emoji - minesweeper - muan， github

［15］ 看B站學物理：掃雷裡的相變 - 梁昊，知乎

編輯：Cloudiiink