15-puzzle 的奇偶可解判定與均勻盤面生成

15-puzzle 有一半排列到不了終盤，Johnson 與 Story 在 1879 年就用奇偶論證說明了這件事。判定時要分欄寬：奇數欄寬看方塊逆序數是否為偶數，偶數欄寬則要加上空格從下數起的列數，合計為奇數才可解。

生成 4×4 盤面，需要均勻抽樣就先均勻打亂，不可解時依固定規則交換兩個非空方塊。想把打亂過程做成動畫，或留下一條走回終盤的路徑，就從終盤隨機滑 k 步並記下移動。

哪一半盤面到不了

把空格也算進排列，每次合法滑動都會翻轉全部 16 格排列的奇偶，也會翻轉空格到右下角的曼哈頓距離奇偶，兩者相加後的奇偶不變。固定交換兩個非空方塊，能把不變量相反的盤面一對一配對，因此兩類一樣大。Johnson 與 Story 在 1879 年還證明，15 puzzle 的同類盤面可以互相到達，終盤所在的那一半全都可解。

Sam Loyd 懸賞 1,000 美元，要求玩家解開把終盤的 14 與 15 對調的題目。空格仍在右下角，排列奇偶卻已翻轉，再怎麼滑也回不到終盤。

16 個位置共有 16! 種排列，因此可達的有 16!/2 ≈ 1.05 × 10^13 個。〈洗牌只有 8,640 萬種：遊戲 RNG 認證在檢查什麼〉算過一副牌的 52! 種排法，這裡的 16!/2 也是同一種計數，只是還要扣掉到不了終盤的那一半。

奇偶判定的兩個分支

棋盤至少有兩列、兩欄，終盤約定方塊從 1 排到 n−1，由左到右、由上到下，空格留在右下角，n 是棋盤總格數。換終盤時，就比較目前盤面與目標盤面的同一個奇偶不變量是否相同。

把盤面依同樣順序排成一列，略過空格，如果前面的數字比後面大，就算一個逆序。程式會檢查每一對方塊，累計逆序數，接著依欄寬分開判定：

奇數欄寬：方塊逆序數為偶數，盤面可解。
偶數欄寬：方塊逆序數加上空格從下數起的列數，合計為奇數，盤面可解。最下面一列算第 1 列。

差別出在垂直滑動。空格水平移動時，略過空格後的方塊順序不變；空格垂直移動時，一個方塊會越過 w−1 個方塊，w 是欄寬。w 為奇數就越過偶數個，逆序數奇偶不變；w 為偶數就越過奇數個，逆序數奇偶會翻轉，空格列數的奇偶也同時翻轉，兩者相加就能抵消。

終盤的逆序數是 0，空格從下數起在第 1 列，所以偶數欄寬那一支要檢查合計是否為奇數。少了列數會判錯；如果改成從 0 開始數，判定也要改成合計為偶數。

小棋盤全列舉驗證

parity_bfs.py 從終盤出發，用 breadth-first search（BFS，廣度優先搜尋）找出所有合法滑動能到的盤面，再列舉全部排列，逐一比較「BFS 有沒有走到」和「判定式說可不可解」。尺寸寫成欄寬 × 列數，0 代表空格：

# Solvability test for sliding puzzles vs. exhaustive BFS on small boards.
# State: tuple of w*h entries, 0 is the blank; goal is 1..w*h-1 followed by the blank.
#   odd width:  solvable iff the inversion count of the tiles is even
#   even width: solvable iff inversions + (row of the blank counted from the bottom, 1-based) is odd
# The rule depends on the goal convention (blank in the bottom-right corner).
from collections import deque
from itertools import permutations

def solvable(state, w):
    tiles = [t for t in state if t]
    inversions = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    if w % 2:
        return inversions % 2 == 0
    blank_row_from_bottom = len(state) // w - state.index(0) // w
    return (inversions + blank_row_from_bottom) % 2 == 1

def reachable(w, h):
    goal = tuple(list(range(1, w * h)) + [0])
    seen, queue = {goal}, deque([goal])
    while queue:
        s = queue.popleft()
        z = s.index(0)
        r, c = divmod(z, w)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < h and 0 <= nc < w:
                l = list(s)
                l[z], l[nr * w + nc] = l[nr * w + nc], 0
                t = tuple(l)
                if t not in seen:
                    seen.add(t); queue.append(t)
    return seen

for w, h in ((2, 2), (2, 3), (3, 2), (3, 3), (4, 2)):
    R = reachable(w, h)
    states = list(permutations(range(w * h)))
    mismatches = sum((s in R) != solvable(s, w) for s in states)
    print(f"{w}x{h}: BFS reachable={len(R):6d} = {w * h}!/2={len(states) // 2:6d}   parity test disagrees on {mismatches} of {len(states)} states")

loyd = tuple(list(range(1, 14)) + [15, 14, 0])   # Sam Loyd's 14-15 swap on 4x4
print("4x4 with 14 and 15 swapped, blank bottom-right: solvable =", solvable(loyd, 4))

2x2: BFS reachable=    12 = 4!/2=    12   parity test disagrees on 0 of 24 states
2x3: BFS reachable=   360 = 6!/2=   360   parity test disagrees on 0 of 720 states
3x2: BFS reachable=   360 = 6!/2=   360   parity test disagrees on 0 of 720 states
3x3: BFS reachable=181440 = 9!/2=181440   parity test disagrees on 0 of 362880 states
4x2: BFS reachable= 20160 = 8!/2= 20160   parity test disagrees on 0 of 40320 states
4x4 with 14 and 15 swapped, blank bottom-right: solvable = False

3×2 與 3×3 驗到奇數欄寬，2×2、2×3 與 4×2 驗到偶數欄寬，所有排列都沒有不一致。最後那個 4×4 盤面只對調 14 與 15，判定結果也如預期是 False。

3×3 的 9! = 362,880 個排列還能全部查過，4×4 的 16! 就不適合用這段程式在筆電上硬算。4×4 可以直接呼叫檢查過的判定函式。

兩種生成器

生成器 A 用 random.shuffle 均勻打亂，不可解就交換由左到右、由上到下找到的前兩個非空方塊。空格不動，交換後仍會選到同一對位置。要取出生成器，只需保留 random 的 import、W 與 H 及 N 的設定，以及 solvable 和 gen_a 函式，將欄寬與列數設成需要的尺寸。BFS、solvable_states 與統計迴圈留在驗證程式裡，否則光是走完全部盤面，就等不到呼叫生成器。

交換兩個方塊會翻轉奇偶，再交換同一對位置，就會回到原盤面，因此不可解盤面與可解盤面一對一配對。在 2×3 上，360 個不可解盤面各自對應到一個可解盤面，加上原本就可解的 360 個，每個可解盤面都有兩個輸入，機率同樣是 2/720。

生成器 B 從終盤出發，每一步等機率選一個合法移動，走滿 k 步就停，沿原路走回去一定有解。uniform_generator.py 在可解集合已知的 2×3 上比較兩種方法，固定 seed 42，每種設定各產生 360,000 個盤面，統計每個盤面的出現次數：

# Two ways to produce a solvable start position, compared on 2x3 where all 360 solvable
# states are known (from BFS), so we can count how often each one comes out.
#   A: shuffle uniformly; if the result is unsolvable, swap the first two tiles (not the blank).
#      Swapping two tiles flips the parity, so this maps the 360 unsolvable states 1-to-1 onto
#      the 360 solvable ones: the output is uniform over solvable states.
#   B: start from the goal and make k random blank moves. Always solvable, but not uniform.
import random
from collections import Counter, deque

random.seed(42)
W, H = 2, 3
N = W * H

def solvable(state, w):
    tiles = [t for t in state if t]
    inv = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    if w % 2:
        return inv % 2 == 0
    return (inv + len(state) // w - state.index(0) // w) % 2 == 1

def moves(s):
    z = s.index(0); r, c = divmod(z, W)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < H and 0 <= nc < W:
            l = list(s); l[z], l[nr * W + nc] = l[nr * W + nc], 0
            yield tuple(l)

goal = tuple(list(range(1, N)) + [0])
seen, q = {goal}, deque([goal])
while q:
    for t in moves(q.popleft()):
        if t not in seen:
            seen.add(t); q.append(t)
solvable_states = seen

def gen_a():
    s = list(range(N)); random.shuffle(s)
    if not solvable(s, W):
        i, j = [k for k in range(N) if s[k]][:2]
        s[i], s[j] = s[j], s[i]
    return tuple(s)

def gen_b(k):
    s = goal
    for _ in range(k):
        s = random.choice(list(moves(s)))
    return s

T = 360_000
for name, gen in (("A: shuffle + parity swap", gen_a), ("B: 20 random moves", lambda: gen_b(20)), ("B: 100 random moves", lambda: gen_b(100))):
    c = Counter(gen() for _ in range(T))
    all_ok = all(s in solvable_states for s in c)
    print(f"{name:26s} all solvable={all_ok}  distinct={len(c):3d}/360  count range {min(c.values()):5d}..{max(c.values()):5d}  (uniform: 1000 each)")

A: shuffle + parity swap   all solvable=True  distinct=360/360  count range   917.. 1103  (uniform: 1000 each)
B: 20 random moves         all solvable=True  distinct=162/360  count range     1..30221  (uniform: 1000 each)
B: 100 random moves        all solvable=True  distinct=180/360  count range   644.. 6203  (uniform: 1000 each)

A 抽到全部 360 個可解盤面，每個出現 917 到 1,103 次，接近均勻抽樣下的期望值 1,000 次，單一盤面出現次數的標準差約 32。

B 走 20 步時，只抽到 162 個盤面，其中有的出現 30,221 次，有的只出現 1 次。走 100 步後，抽到 180 個，出現次數介於 644 和 6,203。count range 只涵蓋出現過的盤面，distinct 是抽到的盤面種類數，剩下的盤面在這批樣本中都沒出現。

把棋盤塗成黑白相間，每滑一步，空格就換一種顏色，盤面圖因此是二分圖。走偶數步，空格只能停在與終盤空格同色的位置，所以這個 2×3 實驗最多只能到達 360 個可解盤面中的 180 個，4×4 也有同樣的一半限制。100 步這次抽齊了那 180 個，20 步其實也能到達這些盤面，只是這次沒有全抽到。有限步數的機率仍受起點影響；混合奇偶步數也不會自動得到均勻分布，因為每步從合法移動中等機率挑選，長期停留比例會與各盤面的合法移動數成正比。

打亂時可以沿原路折返，這個 2×3 棋盤即使隨機走了 100 步，回終盤的最短路徑仍遠小於 100 步。若用最短解步數分級，就得用最佳解求解器算出距離，k 只記錄打亂時走了多遠。

4×4 的距離分布與關卡篩選

4×4 的任何可解盤面都能在 80 次單格移動內解完，而且有盤面需要走滿這個步數，Brüngger 等人在 1999 年證明了這個上限。

Korf 與 Schultze 在 2005 年的〈Large-scale parallel breadth-first search〉算出了完整距離分布，Kociemba 的 15-puzzle solver 頁面列出各個距離的盤面數，以及需要 80 步的 17 個盤面。這份分布可以估計各距離的盤面有多常見，手上盤面的距離仍要逐盤求解。

做出題工具時，要均勻抽取可解盤面就選 A，需要播放打亂過程或回放解法就選 B，並記下每次移動。檢查生成器時，沿用統計程式量盤面覆蓋範圍與出現次數；接成關卡篩選時，讓每個候選盤面先經過最佳解求解器，只保留距離落在指定範圍的盤面，再統計留下的距離分布。小棋盤可以在既有 BFS 裡記錄首次到達的深度，供候選盤面查距離；完整棋盤則逐盤求解。

補充筆記

換終盤時，比較目前盤面與目標的同一個奇偶不變量，別沿用右下角終盤的判定值。
改動判定函式後，用 2×2、2×3、3×2、3×3 與 4×2 的 BFS 全列舉檢查，兩個分支都應與可達集合一致。
改交換規則時，確認交換後仍選到同一對非空位置，一對一配對才成立。
檢查隨機滑 k 步的生成器，要把沒抽到的盤面也算進分布；2×3 可以完整比對，4×4 要避免連驗證程式的全列舉一起搬過去。
4×4 的 16!/2 個可解盤面裡，只有 17 個需要 80 步；篩選這類關卡要看候選盤面的最短解，打亂 80 步不會替你挑出來。