經典遊戲：掃雷的技巧攻略

操作方法

（01）掃雷作爲策略遊戲，需要遊戲者精確的判斷。現在掃雷進階的官方最快紀錄是33.95秒，中級則是由一個波蘭玩家保持的8.5秒。而初級紀錄是1秒，世界上很多人達到了這一點。在1秒的時間裏完成初級掃雷，據測算概率在0.00058％至0.00119％之間（屬於運氣題），最可能的方法是直接點擊四個角的方塊。而本文所作的事情，則是將雷與雷之間的規律給你揪出來，並且深入思考其中的內涵。讓你以後面對掃雷時，縮短與記錄的差距，戰無不勝！從簡單雷區入手     下圖是一個初級的雷區，並且標註了兩顆雷的位置，你能將剩下的地雷掃描出來嗎？經過逐一排查，可以很輕鬆的確定雷區中的6顆地雷所在位置：再來看一個簡單的“雷區”：透過逐步掃描每一個方塊會發現：首先最左邊的和最右邊的兩個格子都一定是地雷，從左數第二個空格子和從右數第二個空格子也都是地雷，由於數字1的關係，從左數第3個格子和從右數第3個格子都不是地雷，翻開一定是數字1……這樣一直下去，最後你會發現最中間的兩個空格子，不管有沒有地雷，都和周圍格子上的數字不符。也就是說這樣的雷區有bug，是無解的。雷區中的邏輯門       怎麼判斷一個雷區是否有bug？又怎麼判斷雷區中地雷的具體位置呢？難道一定要從頭到尾將雷區掃描一遍嗎？其實這些雷區裏其實藏着一個規律。我們用數學方法來分析了上例的雷區：       在之前提到的這兩個雷區裏，把還沒有翻開的格子交叉標記上字母x和x’。可以看到：當x的格子有雷時，x’格子一定沒有地雷，反之亦然。如果將最左邊的空格子作爲輸入，把最右邊的格子作爲輸出，輸入結果和輸出結果一定是一樣或者相反的。如果是相反的，這相當於一個NOT（“非”）門電子元件。如果是一樣的，就有趣了，這樣的一片雷區就具備了電路導線的性質！在這裏，雷區被看成了一個數字邏輯電路。執行這些“或”、“與”、“非”等邏輯運算的電路則被稱爲——邏輯門。任何複雜的邏輯電路都可由這些邏輯門組成。       邏輯門是集成電路上的基本組件。簡單的邏輯門可由晶體管組成。這些晶體管的組合可以使代表兩種型號的高低電平在透過它們後產生信號。而高低電平可以分別代表邏輯上的真假或二進制中的0和1，從而實現邏輯運算。具體到掃雷遊戲裏，也就是說，邏輯門可以用於判斷一系列格子中的地雷的具體位置，而且它如同電路傳導一樣，精確而迅速。       常見的（也是掃雷中用到的）邏輯門包括“與”門、“或”門、“非”門等。將它們組合使用就可以實現更復雜的運算——完成複雜情形下的掃雷，這種方法比按照規則緩慢推進的掃雷方法要節省很多時間。複雜雷區中的精確判斷       在簡單的雷區中小試牛刀後，帶着發現的規律，讓我們進行一次實戰演習。下圖是進階掃雷遊戲中的一個典型的雷區：你能在不翻開格子的情況下，直接指出黃格子中有無地雷嗎？ 如果將雷區隨意改變一點——左上角的一個格子下移一位，結果又如何呢？你可能需要考量全局，從某個點開始逐步推理，將雷區全部掃描一遍，才能判斷。而當雷區任意改變一點時，你都要重新來過，才能再次解答。這無疑是一種巨大成本負擔。     實際上我們可以很快速地給出答案：第一個雷區的黃格子中無雷。而第二個雷區的黃格子中一定有雷。     這是怎麼做到的？其實將上述的邏輯門引入到這個複雜的雷區中，一切都會變得簡單而清晰起來。雷區內靠近邊界、可以直接確定是地雷的位置都插上了標示旗，剩下的位置標上了不同的字母。把一個有地雷格子看作1，沒有地雷的看作0。最左面的格子（u、v）作爲輸入，最右面的格子（t）作爲輸出。按照掃雷遊戲的規則，經過一步步推算，它們之間的關係就是：     ( u , v , t ) = ( 1 , 1 , 1 ) 或 ( 1 , 0 , 0 ) 或 ( 0 , 1 , 0 ) 或 ( 0 , 0 , 0 )     顯然，這個雷區被歸納成了一個AND門，它不僅輕鬆化解了這個掃雷難題，而且把雷區的規律揭示出來了。如此一來，當你掌握掃雷中這些邏輯門規律並加以練習後，就能夠達到精確、快速的“機械化”掃雷水準。而到那時，一個新紀錄或許就會誕生了。數學家的掃雷研究      將掃雷問題抽象化從而縮短遊戲時間的人，也不僅僅是掃雷發燒玩家。一些數學家也十分關注這個遊戲背後的數學意義。      英國一位數學家用掃雷遊戲中的邏輯規律構建了一系列電子元件，用電子電路模擬雷區。他試圖將一個的給定的雷區圖案交由計算機來判斷是否可解。如果隨着格子數量的增加，電腦的計算量增長不是很快，就是P問題，如果計算量增加的很快，就是NP問題。計算機判斷雷區是否可解，需要這類問題屬於P問題纔可以。對於幾種基本的電路元件（AND、OR、NOT），如果將很多個這樣的元件組合起來，相互連接，就會產生很多個輸入、輸出口。判斷最後哪些輸出結果可以產生，哪些不可以產生的這類問題，被稱爲SAT問題，它屬於一個經典的NP完全問題。而英國數學家的這個問題在一些時候等同於一個複雜電子電路的SAT問題，也就是NP完全問題。由此看來，面對一個上千上萬個格子的巨型雷區，不要說去完成所有掃雷任務，就僅僅判斷它是不是可解的，都可能會是計算機也承受不了的的大難題。