數字推盤問題
8-Puzzle（3×3 數字推盤）有一個空格，目標是把打亂的數字排列成有序狀態。
初始狀態（例）：
2 8 3
1 6 4
7 _ 5
目標狀態：
1 2 3
4 5 6
7 8 _
廣度優先搜尋（BFS）
BFS 保證找到最短步數解，但記憶體消耗大。
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 # 無解
3×3 推盤最多 181,440 種排列，BFS 可以處理。
但 4×4 的 15-Puzzle 有 10^13 種狀態，BFS 記憶體不足！
A* 演算法
A* = BFS + 啟發式函數（Heuristic），優先探索「看起來更近目標」的狀態。
評估函數：f(n) = g(n) + h(n)
常用啟發式函數：曼哈頓距離
def manhattan_distance(state, goal):
total = 0
for i, val in enumerate(state):
if val == 0:
continue
goal_idx = goal.index(val)
total += abs(i // 3 - goal_idx // 3) + abs(i % 3 - goal_idx % 3)
return total
import heapq
def astar(start, goal):
h = manhattan_distance(start, goal)
heap = [(h, 0, start, [])] # (f, g, state, path)
visited = {}
while heap:
f, g, state, path = heapq.heappop(heap)
if state in visited and visited[state] <= g:
continue
visited[state] = g
if state == goal:
return path
for next_state, move in get_neighbors(state):
new_g = g + 1
new_h = manhattan_distance(next_state, goal)
heapq.heappush(heap, (new_g + new_h, new_g, next_state, path + [move]))
return None
可解性判斷
不是所有的打亂排列都有解！用「逆序對（Inversions）」判斷：
def is_solvable(tiles, size=3):
flat = [t for t in tiles if t != 0]
inversions = sum(
1 for i in range(len(flat))
for j in range(i + 1, len(flat))
if flat[i] > flat[j]
)
if size % 2 == 1: # 奇數寬度（3×3）
return inversions % 2 == 0
else: # 偶數寬度（4×4）
blank_row = tiles.index(0) // size
return (inversions + blank_row) % 2 == 1
前往數字推盤遊戲，挑戰看你幾步可以解出來！