踩地雷無猜測盤面的生成：首點規則與 solver 驗證

踩地雷即使保證第一下開出一片區域，後面仍可能只剩猜的份。生成無猜測盤面，一個直接的做法是讓 solver 從玩家選的起點解完整盤，只留下能解完的候選盤。Simon Tatham 的 Mines 再加上擾動器，修改 solver 解不下去的盤面，改完重新驗證。

純隨機佈雷與排除首點後均勻佈雷，開區域的機率都有閉式解，可以用 Monte Carlo 核對。整盤則用只有兩條規則的 single-point solver 篩選，Expert 盤面幾乎全被拒絕。

三種「第一下」規則

純隨機佈雷最直接，在所有格子中均勻選出地雷位置，玩家第一下就可能踩雷。若想保證首點安全，可以等玩家選好起點，先把那格排除，再從剩下的格子均勻佈雷。

舊版 Windows 的首點規則是先佈雷，若第一下踩到雷，就把那顆雷搬到最上排從左數第一個空格。這會讓最上排左側的雷密度略高，分布與「排除首點後均勻佈雷」不同，要另外計算機率。Vista 起改成保證首點開出區域。

「開出區域」是指首點顯示 0 並自動展開，以有完整八鄰格的中央格來說，首點本身與周圍 8 格都得無雷，光是點到安全的數字格還不算。

首點開出區域的機率

設盤面共有 N 格、M 顆雷，首點在中央，C(N, M) 表示從 N 格選出 M 格的組合數。純隨機盤共有 C(N, M) 種佈雷方式，要讓中央的 9 格全都安全，地雷就只能放在其餘 N − 9 格，機率是 C(N - 9, M) / C(N, M)。

先排除首點時，所有佈雷方式只剩 C(N - 1, M) 種，符合條件的佈雷方式仍是 C(N - 9, M) 種，因此機率改為 C(N - 9, M) / C(N - 1, M)。這也等於在純隨機模型中，條件設為「首點安全」後，周圍 8 格都無雷的機率，是超幾何分布的一個特例。

first_click.py 對每種盤面與規則各抽樣 200,000 次，seed 固定為 42。exact 是公式結果，MC 是抽樣比例，CI95 是以 1.96 * sqrt(p * (1 - p) / T) 計算的近似 95% 信賴區間半寬，delta 則是 MC - exact。

# Probability that the first click (on the centre cell) opens a region, i.e. shows a zero.
# Two placement rules give two closed forms; both are checked against Monte Carlo (seed 42, 95% CI).
#   random board:            P(9 cells clear) = C(N-9, M) / C(N, M)
#   first click excluded,    P(8 neighbours clear | click cell safe) = C(N-9, M) / C(N-1, M)
#   mines uniform elsewhere:
# Windows' "move the mine to the top-left free cell" rule is a third distribution and is not modelled here.
import math, random

random.seed(42)
boards = {"Beginner 9x9, 10 mines": (9, 9, 10), "Intermediate 16x16, 40": (16, 16, 40), "Expert 30x16, 99": (30, 16, 99)}
T = 200_000
print(f"{'board':24s} {'rule':22s} {'exact':>7} {'MC':>7} {'CI95':>7} {'delta':>7}")
for name, (w, h, m) in boards.items():
    n = w * h
    cx, cy = w // 2, h // 2
    click = cx + cy * w
    nb = {(cx + dx) + (cy + dy) * w for dx in (-1, 0, 1) for dy in (-1, 0, 1)} - {click}
    for rule, exact in (("random board", math.comb(n - 9, m) / math.comb(n, m)), ("click excluded", math.comb(n - 9, m) / math.comb(n - 1, m))):
        hits = 0
        for _ in range(T):
            pool = range(n) if rule == "random board" else [i for i in range(n) if i != click]
            mines = set(random.sample(pool, m))
            hits += click not in mines and not (mines & nb)
        p = hits / T
        ci = 1.96 * math.sqrt(p * (1 - p) / T)
        print(f"{name:24s} {rule:22s} {exact:7.4f} {p:7.4f} {ci:7.4f} {p - exact:+7.4f}")

board                    rule                     exact      MC    CI95   delta
Beginner 9x9, 10 mines   random board            0.2855  0.2852  0.0020 -0.0002
Beginner 9x9, 10 mines   click excluded          0.3257  0.3270  0.0021 +0.0013
Intermediate 16x16, 40   random board            0.2110  0.2089  0.0018 -0.0021
Intermediate 16x16, 40   click excluded          0.2501  0.2495  0.0019 -0.0006
Expert 30x16, 99         random board            0.1226  0.1226  0.0014 +0.0000
Expert 30x16, 99         click excluded          0.1545  0.1533  0.0016 -0.0012

Expert 的中央首點，在純隨機盤開區域的機率約 12.3%，先排除首點後約 15.4%。

Intermediate 純隨機盤的 delta 是 −0.0021，絕對值超過 CI95 的 0.0018，約差 2.3 個標準誤。95% 信賴區間仍可能漏掉精確值，六組比較中出現一次並不奇怪。

Kostka 的開區域機率隨點擊位置而變，Beginner 介於 0.19 到 0.60，Intermediate 介於 0.21 到 0.60，Expert 則介於 0.12 到 0.50。邊角需要同時無雷的鄰格較少，比中央格更容易開出區域。

首點規則怎麼選

第一下開出區域後，其他地方仍可能出現 50/50：兩格之中有一顆雷，現有線索無法分辨位置，也沒有其他線索可用。

只要求第一下安全，就把點擊格排除在佈雷範圍外；要讓第一下展開區域，連它的鄰格也一起排除。

Tatham 的 solver 加擾動器

Tatham 的生成器等玩家點了第一下才開始佈雷，同一張盤面換個起點，可解性可能不同。

solver 只用玩家看得到的線索推理，解不下去時，擾動器通常在未開區域搬雷，讓推理能繼續；接近結束、沒有其他未開格可放時，也可能把雷移進已開區域。修改可能破壞先前用過的線索，即使這輪解完，仍要清空解題狀態，從同一起點重跑。完全不靠擾動就解完，盤面才能交給玩家。Tatham 用每輪需要的擾動次數判斷進展，次數減少就繼續，反而增加就放棄這張盤面、重新生成。

這是啟發式做法，沒有保證每次生成都會成功。Tatham 的預設雷密度超過 Windows 標準兩倍，仍能生成可解的盤面。

只要推理規則正確，弱 solver 通過的盤面也確實能不猜解完；加強 solver 可以讓更多盤面通過，但不代表玩家更容易看出解法。除錯時也要能重現同一張盤面，seed 的管理見〈遊戲 RNG 正式環境要猜不到、測試要能重播：在 Go 裡把兩件事切開〉。

一個簡單 solver 能解完多少

single_point_solver.py 只看單一數字周圍的格子，反覆套用兩條規則：

數字扣掉已插旗數，剛好等於未開且未插旗的鄰格數，這些格子就全是雷，全插旗。
已插旗數等於數字，其餘未開且未插旗的鄰格就全安全，全開。

每種難度測 2,000 張盤面，seed 固定為 42。每張盤都從中央開始，地雷均勻放在首點周圍 3×3 安全區之外，遇到 0 就展開，兩條規則都無法再推進時停止，只有開完所有安全格才算成功。

# How often can a simple "single point" solver finish a board without guessing?
# Boards: Beginner/Intermediate/Expert, first click on the centre, mines placed uniformly
# outside the 3x3 block around the click (so the first click always opens a region).
# Solver rules, applied until nothing changes:
#   - a revealed number whose hidden neighbours all must be mines -> flag them
#   - a revealed number whose flagged neighbours already satisfy it -> open the rest
# This measures what THIS solver can finish, not whether a board is logically guess-free.
import random

random.seed(42)

def neighbours(i, w, h):
    x, y = i % w, i // w
    return [(x + dx) + (y + dy) * w for dx in (-1, 0, 1) for dy in (-1, 0, 1)
            if (dx or dy) and 0 <= x + dx < w and 0 <= y + dy < h]

def solve(w, h, m, click):
    n = w * h
    safe_zone = set(neighbours(click, w, h)) | {click}
    mines = set(random.sample([i for i in range(n) if i not in safe_zone], m))
    count = [sum(j in mines for j in neighbours(i, w, h)) for i in range(n)]
    opened, flagged = set(), set()
    def open_cell(i):  # flood fill through zeros
        stack = [i]
        while stack:
            c = stack.pop()
            if c in opened: continue
            opened.add(c)
            if count[c] == 0:
                stack.extend(j for j in neighbours(c, w, h) if j not in opened)
    open_cell(click)
    changed = True
    while changed:
        changed = False
        for i in list(opened):
            if count[i] == 0: continue
            hidden = [j for j in neighbours(i, w, h) if j not in opened and j not in flagged]
            flags = sum(j in flagged for j in neighbours(i, w, h))
            if hidden and flags + len(hidden) == count[i]:
                flagged.update(hidden); changed = True
            elif hidden and flags == count[i]:
                for j in hidden: open_cell(j)
                changed = True
    return len(opened) == n - m

T = 2000
for name, (w, h, m) in {"Beginner 9x9/10": (9, 9, 10), "Intermediate 16x16/40": (16, 16, 40), "Expert 30x16/99": (30, 16, 99)}.items():
    done = sum(solve(w, h, m, (w // 2) + (h // 2) * w) for _ in range(T))
    p = done / T
    print(f"{name:24s} single-point solver finishes without guessing: {p:.3f} +/- {1.96 * (p * (1 - p) / T) ** 0.5:.3f}  (n={T})")

Beginner 9x9/10          single-point solver finishes without guessing: 0.637 +/- 0.021  (n=2000)
Intermediate 16x16/40    single-point solver finishes without guessing: 0.241 +/- 0.019  (n=2000)
Expert 30x16/99          single-point solver finishes without guessing: 0.001 +/- 0.001  (n=2000)

Beginner 約 64% 能解完，Intermediate 約 24%，Expert 約 0.1%。輸出的 +/- 沿用常態近似公式，但 Expert 成功次數太少，95% 區間的下限在四捨五入前已落到零以下，應改用 Wilson 區間估計。

若線索指出兩組未開格需要相同的雷數，而其中一組完全包含於另一組，多出來的格子就能判定安全。single-point solver 不會合併線索做這種子集推理，也沒有利用全域雷數約束或列舉可能的佈雷，有些還能推進的盤面就這樣被放棄了，所以它的失敗比例不等於必須猜測的比例。

實作生成器可以先用隨機重試。這份測量程式在解題函式裡佈雷，最後只回傳是否成功；要接成篩選步驟，就把佈雷搬到外層，保留候選盤，再交給 solver，通過才回傳同一張盤面。失敗就重新抽樣，達到嘗試次數或等待時間上限便回報生成失敗。Expert 的候選盤大多會被這個 solver 拒絕，先量單次驗證耗時與取得可用盤面的等待時間；等得太久，再比較加強 solver 或加入 Tatham 擾動器後的完整生成時間。

NP-complete 對 solver 的影響

Kaye 在 2000 年的《Mathematical Intelligencer》22（2），第 9 到 15 頁，證明 Minesweeper Consistency Problem 是 NP-complete：給定局部盤面與數字，判斷是否存在與線索一致的佈雷。P vs NP 是 Clay 數學研究所的百萬美元獎問題之一。

這個問題允許任意大小與形狀的一般化輸入，solver 可以列舉所有可能的佈雷，代價是最壞情況會很慢。某張盤面留下無法區分的 50/50，則是現有線索不足，就算把可能的佈雷全查過，仍無法確定該開哪格。

補充筆記

選首點公式時，先確認佈雷規則：純隨機盤用 C(N - 9, M) / C(N, M)，排除首點後均勻佈雷用 C(N - 9, M) / C(N - 1, M)，Expert 的中央開區域機率約為 12.3% 與 15.4%。踩雷後搬到固定位置要另算分布。
採用 Tatham 的擾動方式後，要從玩家選的同一起點完整重跑 solver，通過才交出盤面。
single-point solver 在 Beginner 約 64%、Intermediate 約 24%、Expert 約 0.1% 能解完。用它篩 Expert 盤面時，先量取得可用盤面的等待時間，再決定是否加強推理或加入擾動。
判斷局面是否必須猜，要檢查現有線索能否確定安全格；Kaye 的 NP-complete 結論處理一般化輸入的 consistency problem。