# 15-puzzle 的奇偶可解判定與均勻盤面生成 > 15-puzzle 均勻生成可解盤面的做法是先均勻打亂，不可解就依固定規則交換兩個非空方塊。從終盤隨機滑 k 步能保證可解，但固定 k 最多只能到達一半可解盤面。 原文：https://sheng.page/posts/fifteen-puzzle-uniform-solvable-board-generation/ · 發布：2026-10-26 · 作者：Sheng 15-puzzle 有一半排列到不了終盤，Johnson 與 Story 在 1879 年就用奇偶論證說明了這件事。判定時要分欄寬：奇數欄寬看方塊逆序數是否為偶數，偶數欄寬則要加上空格從下數起的列數，合計為奇數才可解。 生成 4×4 盤面，需要均勻抽樣就先均勻打亂，不可解時依固定規則交換兩個非空方塊。想把打亂過程做成動畫，或留下一條走回終盤的路徑，就從終盤隨機滑 k 步並記下移動。 ## 哪一半盤面到不了 把空格也算進排列，每次合法滑動都會翻轉全部 16 格排列的奇偶，也會翻轉空格到右下角的曼哈頓距離奇偶，兩者相加後的奇偶不變。固定交換兩個非空方塊，能把不變量相反的盤面一對一配對，因此兩類一樣大。Johnson 與 Story 在 1879 年還證明，[15 puzzle 的同類盤面可以互相到達](https://en.wikipedia.org/wiki/15_puzzle)，終盤所在的那一半全都可解。 Sam Loyd 懸賞 1,000 美元，要求玩家解開[把終盤的 14 與 15 對調的題目](https://en.wikipedia.org/wiki/15_puzzle#Sam_Loyd)。空格仍在右下角，排列奇偶卻已翻轉，再怎麼滑也回不到終盤。 16 個位置共有 16! 種排列，因此可達的有 `16!/2 ≈ 1.05 × 10^13` 個。〈[洗牌只有 8,640 萬種：遊戲 RNG 認證在檢查什麼](/posts/game-rng-certification/)〉算過一副牌的 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 代表空格： ```python # 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)) ``` ```text 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 個盤面，統計每個盤面的出現次數： ```python # 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)") ``` ```text 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 年證明了這個上限](https://en.wikipedia.org/wiki/15_puzzle)。 Korf 與 Schultze 在 2005 年的〈Large-scale parallel breadth-first search〉算出了完整距離分布，[Kociemba 的 15-puzzle solver 頁面](https://kociemba.org/themen/fifteen/fifteensolver.html)列出各個距離的盤面數，以及需要 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 步不會替你挑出來。 ## 延伸閱讀 - Wikipedia〈[15 puzzle](https://en.wikipedia.org/wiki/15_puzzle)〉：1879 年的奇偶證明與 Sam Loyd 懸賞，以及 80 步上限。 - Herbert Kociemba〈[15-Puzzle Optimal Solver](https://kociemba.org/themen/fifteen/fifteensolver.html)〉：完整距離分布與需要 80 步的 17 個盤面，引用 Korf 與 Schultze 的 2005 年論文。 > 想法與技術判斷出自 Sheng，和 Claude 一起起草 · 範例在 Mac 上以 Python 3.15.0 實測。