數字推盤怎麼最短路徑解？BFS 與 A* 演算法入門

數字推盤問題

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)

• g(n)：從起點到 n 的實際步數
• h(n)：從 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

前往數字推盤遊戲，挑戰看你幾步可以解出來！