BFS 與 A* 演算法入門
問題定義
8-Puzzle（3×3 數字推盤）有一個空格，目標是把打亂的數字用最少步數排列成有序狀態（1~8 從左到右、從上到下）。整個問題空間有 181,440 種合法排列，需要有效率的搜尋演算法。
廣度優先搜尋（BFS）
一層一層從起點向外擴展，保證找到最短步數解。缺點是每個狀態都要存下來，記憶體消耗隨步數指數增長。3×3 可以撐住，4×4 的 15-Puzzle 就爆炸了。
A* 演算法
BFS + 啟發式函數，優先探索「看起來更近目標」的狀態。評估函數 f(n) = g(n) + h(n)，其中 g 是已走步數，h 是到終點的估計（曼哈頓距離）。比 BFS 快幾十倍。
BFS 核心程式碼（Python）
from collections import deque
def bfs(start, goal):
queue = deque([(start, [])]) # (目前狀態, 移動路徑)
visited = {start}
while queue:
state, path = queue.popleft()
if state == goal:
return path # 找到最短路徑！
for next_state, move in get_neighbors(state):
if next_state not in visited:
visited.add(next_state)
queue.append((next_state, path + [move]))
return None # 無解（此排列不可達）A* 的啟發式：曼哈頓距離
def manhattan_distance(state, goal):
total = 0
for i, val in enumerate(state):
if val == 0:
continue # 空格不計算
goal_idx = goal.index(val)
row_diff = abs(i // 3 - goal_idx // 3)
col_diff = abs(i % 3 - goal_idx % 3)
total += row_diff + col_diff
return total
# 例：數字 5 在位置 (2,1)，目標是 (1,1)
# 曼哈頓距離 = |2-1| + |1-1| = 1計算機會自動判斷你的初始盤面是否有解（有一半的排列是無解的！），並提供最優步數提示。