HDU 1043 Eight - 八數碼問題 A* 求解

題目大意

經典 8-puzzle (3×3 九宮格)，數字 1~8 和一個空格 'x'。合法移動：空格與上下左右相鄰數字交換。給定初始狀態，求達到目標狀態 12345678x 的最短移動序列（輸出 u/d/l/r 字符串）。無解輸出 unsolvable。

可解性判斷：逆序數奇偶性

將棋盤攤平為一維數組（忽略 x），計算逆序對數。逆序數為偶數 ⇔ 可解。目標狀態逆序數為 0（偶），故初始狀態逆序數必須為偶。

A* 算法設計

• 狀態編碼：康拓展開 (Cantor Expansion) 將排列映射為唯一整數 [0, 9!-1]，作為訪問標記數組下標。
• 啟發函數 h：曼哈頓距離和 — 每個數字到其目標位置的 |dx|+|dy| 之和。可接受、單調，保證 A* 最優。
• 優先隊列：按 f = g + h 排序，g 為已走步數。
• 路徑記錄：記錄每個狀態的前驅狀態與操作字符，終態回溯構建路徑。

關鍵代碼框架 (C++)

#include 
using namespace std;

const int FACT[9] = {1,1,2,6,24,120,720,5040,40320};
const int GOAL_HASH = 322560; // "12345678x" 的康拓值

struct Node {
    int grid[3][3];
    int x, y;       // 空格位置
    int g, h;       // g=實際步數, h=啟發值
    int hash;       // 康拓值
    bool operator<(const Node& o) const {
        return f() != o.f() ? f() > o.f() : g > o.g(); // 小頂堆
    }
    int f() const { return g + h; }
    bool isGoal() const { return hash == GOAL_HASH; }
};

int cantor(int grid[3][3]) { /* 計算康拓值 */ }
int manhattan(int grid[3][3]) { /* 計算曼哈頓距離和 */ }
void expand(Node u, vector& next) { /* 生成四個方向移動後的新狀態 */ }

int main() {
    // 讀入初始狀態
    Node start;
    // ... 初始化 start.grid, x, y, g=0, h=manhattan, hash=cantor

    // 可解性檢查
    if (!solvable(start)) { cout << "unsolvable\n"; return 0; }

    // A*
    priority_queue pq;
    vector visited(9*FACT[8], -1); // 前驅哈希
    vector action(9*FACT[8]);     // 到達該狀態的操作
    pq.push(start);
    visited[start.hash] = -2; // 起點標記

    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        if (u.isGoal()) { /* 回溯輸出路徑 */ break; }
        vector next;
        expand(u, next);
        for (Node& v : next) {
            if (visited[v.hash] == -1) {
                visited[v.hash] = u.hash;
                action[v.hash] = v.op; // 'u','d','l','r'
                pq.push(v);
            }
        }
    }
    return 0;
}

優化細節

• 康拓展開/折疊：預計算階乘，O(9²) 可接受；亦可用 64 位整數位掩碼編碼狀態（每格 4 位），更快。
• 雙向 BFS：從起點和終點同時搜索，相遇時合併路徑，大幅減少狀態數（本題單向 A* 也能過）。
• 優先隊列 tie-break：f 相同時優先 g 大的（更接近目標），或按操作字典序保證輸出字典序最小路徑。

總結

八數碼是 A* 算法的經典教學案例。關鍵組件：狀態編碼 (康拓/位掩碼)、可接受啟發函數 (曼哈頓距離)、優先隊列、路徑回溯。掌握本題可舉一反三解決十五數碼、華容道等滑塊謎題。