數學家的掃雷研究
將掃雷問題抽象化從而縮短遊戲時間的人,也不僅僅是掃雷發燒玩家。一些數學家也十分關注這個遊戲背後的數學意義。
英國一位數學家用掃雷遊戲中的邏輯規律構建了一係列電子元件,用電子電路模擬雷區。他試圖將一個的給定的雷區圖案交由計算機來判斷是否可解。如果隨著格子數量的增加,電腦的計算量增長不是很快,就是P問題,如果計算量增加的很快,就是NP問題。計算機判斷雷區是否可解,需要這類問題屬於P問題才可以。
對於幾種基本的電路元件(AND、OR、NOT),如果將很多個這樣的元件組合起來,相互連接,就會產生很多個輸入、輸出口。判斷最後哪些輸出結果可以產生,哪些不可以產生的這類問題,被稱為SAT問題,它屬於一個經典的NP完全問題。
而英國數學家的這個問題在一些時候等同於一個複雜電子電路的SAT問題,也就是NP完全問題。由此看來,麵對一個上千上萬個格子的巨型雷區,不要說去完成所有掃雷任務,就僅僅判斷它是不是可解的,都可能會是計算機也承受不了的的大難題。