有時,，當邊肖回憶他的童年和青年時代時，他總是看到藍天和嫩草,，以及他以前和朋友們在那里度過的快樂時光.

當然,，不要誤會。

我說的藍天綠草,，就是這個意思,。

為了防止被打，邊肖選擇了提前打爆自己的腦袋,。

Windows XP確實承載了很多回憶,，XP真的很有用。Windows XP于2001年8月24日正式發(fā)布,，微軟于2014年4月8日停止支持Windows XP桌面系統(tǒng),。直到2019年4月9日這個星期二，最后一批運行在嵌入式設(shè)備上的Windows XP才失去了官方支持,。Xps終于正式和我們說再見了,。[1]

經(jīng)典掃雷游戲

說到XP，不得不說操作系統(tǒng)自帶的掃雷,、接龍等經(jīng)典游戲真的很經(jīng)典,，很好玩，也很耗時間,。如果能把全人類花在這上面的時間都算上,，估計是個天文數(shù)字。不過,，雖然《掃雷》已經(jīng)玩了很久很久,，玩了很多次，但我估計99%的玩家都沒想過,，為什么自己死這么容易,。

對比別人家孩子玩掃雷的速度。

畫面加速,。如果想看目前世界上最快掃雷的紀錄,，可以去【2】觀看。

看你自己玩掃雷,。

差不多到這個程度了,，地雷一到掃雷圖標就已經(jīng)爆炸了。

雖然XP已經(jīng)離我們遠去,，但好在Win10系統(tǒng)還可以直接在商店搜索“掃雷”下載官方重置的掃雷游戲,，重新體驗以前的經(jīng)典。

其實很多科學(xué)家也喜歡玩掃雷。但是如果大部分人在玩掃雷的時候死的很快,，那么他們會一直重開,，直到遇到一個好的開始(然后死的很快)?？茖W(xué)家不一樣,。如果他們玩掃雷死的快，就不會重開了,。他們會直接證明“這個游戲過關(guān)概率為零”,。

畢竟掃雷歷史悠久，有大量的論文分析解決掃雷游戲的概率,。作為一個熟練點擊掃雷艇重啟按鈕的手殘掃雷艇,，今天我就系統(tǒng)的和大家聊聊掃雷艇背后的故事。

掃雷秘籍

掃雷小抄

天下武功無敵,，唯快不破,！

從數(shù)學(xué)上講，掃雷相當于一個不斷給你已知條件,，不斷求解的過程,，就像一道條件遞增的應(yīng)用題?？梢杂米箧I點擊不是雷的塊,，用右鍵標出你認為是雷的區(qū)域。如果你點擊的棋子不是一個雷,，它會告訴你這個區(qū)域周圍的八個方格里有多少個雷,。只要你點得夠快，雷是追不的,。

通過一個非常簡單的歸謬法,，我們可以推斷出很大一部分礦井的位置。[3]

角落里的情況

所謂歸謬法,，就是逆向思考這個問題,。如果有這樣的凹角，里面是空白的,，但是角是1，那么這個角一定有雷,。因為如果這個地方不再是雷,，那么中間1所指的雷就只能流浪了。同樣,，如果一個邊上有一個3,，那么3旁邊的三個一定是雷霆。畢竟礦哥擠不進一個格子。

邊境的局勢

除了這種歸謬法,，掃雷還有很多固定的“套路”,。學(xué)會這個套路，保證你的掃雷技能大幅度提升,，躋身掃雷社區(qū)500強,。

聽起來像是非常強大的東西。

其實我們在掃雷中經(jīng)常會遇到一些固定的數(shù)字,，比如連續(xù)三個數(shù)字121,。這時候不用想，直接在121里兩個1反方向標礦就可以了,?；蛘咚膫€連號1221，此時兩個2的反方向也一定是雷霆,。

在121的情況下,，由于左邊1的限制，黃域只能有一個灰色,，而中間2至少需要2個灰色,，所以粉色的一定是雷霆。同樣,，證明對方

在1221的情況下,，和上面的證明過程一樣，由于1的限制,，黃域只能有1個灰,，所以2對面的另一個方塊一定是雷。

“邊肖邊肖,，我有一個問題,。121221呢？如果按照秘籍填礦,，中間那個附近有兩個礦嗎,？」

好像有問題？

“這種情況是不可能的,！從左邊數(shù)的三個一已經(jīng)覆蓋了上面所有的未知空間,，所以地雷最多只有三個。但是下面顯示的地雷數(shù)量是1 2 2 1 2 1,，只重復(fù)數(shù)中間的五個方塊就是7,，是3的兩倍多。所以這種圖形是不可能的,！」

咳咳,，收回你的想法,。如上所述，掃雷確實有一些套路,。每天看這本掃雷秘籍,，久而久之，掃雷技能一定會很棒,。

掃雷還是運氣,？

幸運與否，這是個問題

玩掃雷,，就得接受,。這是一場性格游戲。

雖然生活已經(jīng)如此艱辛,，但我還是要毫不留情地揭露,。我想此時你已經(jīng)掌握了掃雷的套路，但是有時候還是要面對猜雷這種事情,，一著不慎滿盤皆輸,。

猜猜黃色部分的雷應(yīng)該怎么分配？

圖中黃色部分是典型的掃雷問題,，需要猜,。根據(jù)角落里的數(shù)字，只能知道12黃色部分一定只有一個雷,，但不知道哪個是雷,。如果沒有其他信息，我們已經(jīng)努力了大半個棋盤,，最終通過這個雷區(qū)的概率仍然只有1/8,。

這個簡單的判斷就可以了，有時候會遇到一些比較隱晦的猜測,。

掃雷判斷題

假設(shè)我們在掃雷的過程中遇到這樣的模式,，那真的是一件讓人哭笑不得的事情。如果你不知道怎么哭,，你可以先準備好眼淚,，邊肖會馬上告訴你為什么哭。從左邊開始,，假設(shè)第一個空位被雷劈,，然后第二個空位被雷劈，因為空位中間有一個1,，所以第三個空位被雷劈,，以此類推。但如果第一個空位沒有雷,，第二個空位有雷,，那就說得通了?？觳鹊乩琢?，還是這么復(fù)雜的問題，至于嘛,。

別急,，后面還有更復(fù)雜的。這里的X上有沒有雷,，后面的*都是一樣的,，所以這個雷區(qū)就像一根傳遞信號的電線。在掃雷地圖上,，我們不僅可以制作這種簡單的導(dǎo)線來傳輸信號,，還可以實現(xiàn)所有電子電路中邏輯門的運算。[4,5]

非門電路

或門電路

這是兩個“簡單”的邏輯門,，分別實現(xiàn)非門翻轉(zhuǎn)信號和或門對兩個信號進行或運算,。在另一款知名沙盒游戲《—— 《我的世界（Minecraft）》中，玩家也可以利用游戲中的素材,，紅石(實際上是Windows 10操作系統(tǒng)在此之前的年度更新代碼都是以紅石命名的)來實現(xiàn)各種復(fù)雜的邏輯運算,，甚至有玩家在《我的世界》用紅石打造了一臺真正的運行電腦。

Redstone計算機,，配有完整的寄存器,、加法器和其他組件[6]

算了，不敢想象掃雷會是什么樣子,。

很難判斷是否有解決方案,。

找答案

回到文章開頭，如果解決了一個掃雷問題,，我們就很容易死掉,。如果我們把這個問題交給計算機呢？然而不幸的是,，在正常情況下,，計算機仍然無力解決掃雷問題。

困難的

好在在我們平時玩的小棋盤下,，電腦也可以通過搜索得到答案,。

為了理解計算機處理的幾個難度級別，首先要知道——多項式時間的概念,。對于同一個算法,，根據(jù)問題的大小，計算機一般需要不同的時間來計算,。舉個最直觀的例子,，小明要去洗衣服,。他洗一件衣服需要2分鐘，洗五件衣服需要10分鐘,，洗十件衣服需要20分鐘,。處理問題的時間與問題的規(guī)模成線性關(guān)系，是多項式?，F(xiàn)在我們假設(shè)小明還是要洗衣服的,，只是他現(xiàn)在的衣服比較特殊。這種衣服他洗一件要2分鐘,，但洗五件要32分鐘,，洗十件要1024分鐘。這個時間是指數(shù)的,，不是多項式的,。評價一個算法，隨著問題規(guī)模的增大,，如何增加計算時間是一個很重要的指標,。

在計算機中，我們?nèi)匀徽J為多項式時間是很快的,。如果按照解決的難易程度對問題進行分類,，P指的是多項式時間內(nèi)可以解決的問題。俗話說,，是一個可以快速計算的問題,。NP指的是一個計算不一定很快的問題，但是我們可以很快查到任何答案,。NP完全問題是比所有NP問題都難的NP問題,。雖然人有美好的想法，但總覺得查的快,，要想辦法讓他算的快,，但目前還是未知數(shù)。[7]

不幸的是,，求解一個掃雷游戲的解,，恰恰是NP完全問題——中最難的一類，很容易驗證結(jié)果正確與否,。到目前為止,，人們還沒有找到一個多項式時間算法來解決這類問題，通常只有指數(shù)甚至階乘搜索算法才能解決,。

一種用于顯示液晶數(shù)字的邏輯電路,。我們可以很容易的一個一個試，但是反過來就很難了,，尤其是這個邏輯電路非常大的時候,。

掃雷游戲就屬于這樣的難題,，原因是上一章提到的。掃雷游戲可以看作是一個用邏輯門進行運算的邏輯電路,。給定一個邏輯電路,，在輸出結(jié)果已知的情況下,，能否確定每個輸入的值,？這個問題叫做SAT問題，是世界上第一個被證明是NP完全的問題,。[8]這種問題很容易驗證,。你只需要把結(jié)果代入邏輯電路就能立刻知道是否滿足要求，但是計算滿足結(jié)果的輸入是極其麻煩的,。

求解掃雷游戲的結(jié)果,，用那些構(gòu)造的邏輯門，正好等價于求解SAT問題,。[9]

掃雷也與滲透有關(guān),。

預(yù)膨脹

液體，圖片來自Giphy,，Michael Shillingburg

其實我們覺得掃雷游戲很難玩,。其實還有一個原因。這個原因和物理學(xué)中的滲透有關(guān),。

20世紀60年代,，科學(xué)家[10]發(fā)現(xiàn)當流體流經(jīng)多孔介質(zhì)時，介質(zhì)中的孔洞總是被堵塞,，有時會影響流體的流出,。更奇怪的是，當這些多孔介質(zhì)中孔隙被隨機堵塞的比例逐漸增大到一定值時,，起初還能流動的流體突然被完全堵塞,。當孔洞被隨機堵塞的概率發(fā)生變化時，液體流動的速率也會發(fā)生突變,。

這種現(xiàn)象被稱為預(yù)膨脹,。[11]

在這種情況下你應(yīng)該怎么做？

在掃雷中,，也有類似的滲濾現(xiàn)象,。當一個游戲中的地雷密度特別低的時候，我們幾乎是隨便點一下,，也不會點地雷,，而是點大面積的空白處，一下子解決問題,。但是,，當?shù)氐乩酌芏仍黾拥揭欢ǔ潭群?，即使我們理性分析，絕不妄加猜測,，也不可能把掃雷的問題搞對,。

針對不同的棋盤尺寸，有人計算了不同地雷密度下的獲勝概率,。三角形所對應(yīng)的曲線,，原色是88，正方形是1513,，菱形是3016,。這里的解實際上是否不包括第一次隨機點擊踩雷的概率。[12]

如果我們抽象出流體通過多孔介質(zhì)滲流的模型,，實際上對應(yīng)的是點滲流,，即把整個介質(zhì)想象成一個網(wǎng)絡(luò)，當流體通過每個網(wǎng)格時,，可能以概率p通過,，如果不能流過的網(wǎng)格在網(wǎng)絡(luò)中連成片，流體就不能流過,。

嚴格來說,，解決掃雷問題其實和逾滲模型很像。其實我們的求解過程也像一臺推土機,，不斷利用已有的知識將已知區(qū)域一層層往外推,。如果游戲中某處的地雷密度較高，那么可溶部分被地雷分離的可能性較大,。礦井密度和滲流參數(shù)起著同樣的作用,。如果分離到無法連接整個棋盤的地步，就無法繼續(xù)推理,。更嚴謹?shù)淖C明,，請參考Elchanan Mossel的論文。[13]

推土機,，圖片來自網(wǎng)絡(luò),。

隨著格子的增加，這條勝率曲線的中間部分越來越陡,，掃雷問題正在向兩個極端發(fā)展：要么根本解決不了,，要么很容易解決。在進階模式下,，地雷的密度其實已經(jīng)達到了99/480=0.2,，能夠解決的概率不到1/4。這還不算手抖的有點不對勁，起步不好的情況,。真的不友好,。

結(jié)論

結(jié)論

表情符號版掃雷[14]

我相信看到這個地方的人

一定渴望玩掃雷。