踩地雷以電腦附贈的小遊戲聞名,不過在數學與電腦的研究裡也曾引起討論。關鍵字是「NP完全」。

踩地雷是NP完全

2000年前後,數學家理查.凱(Richard Kaye)證明了,和踩地雷有關的下列問題,屬於稱為「NP完全」的困難問題之一。

給定一個寫有數字的盤面,是否存在至少一種地雷擺法,和這些數字都不矛盾。

平常玩的時候思考的「這一格安不安全」,也和這個問題有很深的關係。

什麼是NP完全

簡單來說,NP完全是具有以下性質的問題。

  • 確認答案正不正確很簡單: 只要有人給你看一種地雷擺法,是否和所有數字相符,馬上就能確認。
  • 找出答案很費力(一般認為如此): 盤面一大,擺法的候選數量就會暴增。目前已知的任何方法,都還沒有找到能對任何盤面都快速找出答案的。

而且已經知道,NP完全的問題之間可以互相轉換。只要其中一個找到任何情況下都能快速解開的方法,其他NP完全的問題也就全部能快速解開。這個「有沒有快速解開的方法」,就是著名的未解難題「P≠NP猜想」,也是懸賞100萬美元的難題之一。

擺法的數量很快就會變得龐大

調查擺法之所以費力,是因為候選的數量變得非常龐大。

  • 在9×7的盤面擺8顆地雷,擺法是從63格中選8格的組合數,約39億種。
  • 在26×15的盤面擺75顆地雷,擺法是從390格中選75格的組合數,是超過80位數的數字。

當然,實際玩的時候不需要全部調查。沒有接觸數字的格子可以合在一起考慮,多數情況只要看一兩個數字就能決定。即使如此,在數字複雜交錯的情況下,要確實得出答案有時還是很費力。

App 只挑選人靠推理就能解開的盤面

App「踩地雷」在產生盤面時,會確認是否只靠人會用的以下3個規則,就能從頭解到尾。

  1. 從一個數字能得知的事
  2. 組合兩個數字能得知的事
  3. 從整個盤面剩餘的地雷數能得知的事

每個規則要看的範圍都很小,能很快調查完。這3個規則解不開的盤面,會移動地雷重新製作。因此玩的人也不需要用調查所有擺法那種沉重的思考方式,就一定能解到最後。

本站的文章裡可以玩的盤面也是用同樣的想法製作的。在電腦上測量產生與★5相同大小盤面的時間,每個盤面平均只要幾毫秒。

益智遊戲與數學

數獨等許多其他紙筆益智遊戲,在盤面放大的一般形式下,也已知是NP完全。人能玩得開心的益智遊戲,很多都設計成「不必全部調查,也能循著脈絡解開」。App「踩地雷」的免猜測盤面,也是其中之一。

關於機率的計算,在踩地雷的機率裡有介紹。