八數碼問題：雙向 BFS + 康托展開求解

問題描述

3×3 九宮格，數字 1~8 和空格 'x'。從給定初始狀態移動空格，使其變為目標狀態 12345678x。輸出移動序列（u/d/l/r），或 unsolvable。

核心技術

1. 狀態表示與康托展開

將 9 位排列映射為唯一整數（1~9!），用於訪問標記。康托展開公式：

hash = 1 + Σ_{i=0}^{8} (小於 a[i] 且在 i 後的數的個數) * (8-i)! 

2. 雙向 BFS

從初始態和目標態同時 BFS，相遇時合併路徑。大幅減少搜索空間（單向 BFS 狀態數 9!/2 ≈ 18萬，雙向僅需擴展約 2×√18萬 ≈ 8000）。

3. 路徑記錄

每個狀態存儲父節點指針與移動方向，相遇時回溯拼接路徑。注意雙向 BFS 合併時，反向搜索的移動方向需取反（u↔d, l↔r）。

可行性判斷

八數碼有解當且僅當初始態與目標態的逆序數奇偶性相同。逆序數：將 'x' 視為 9 或忽略，計算排列中較大數在較小數前的對數。

代碼框架（雙向 BFS + 康托）

struct Node {
    int s[9], pos, hash;
    string path;
};
int cantor(int s[]) { /* 康托展開 */ }

string bfs_bidirectional(int start_hash, int goal_hash) {
    queue q1, q2;
    unordered_map vis1, vis2;
    // 初始化 start 和 goal 節點，入隊
    // 交替擴展 q1 和 q2，檢查是否相遇
    // 相遇時合併路徑返回
    return "unsolvable";
}

其他算法對比

• A* + 曼哈頓距離啟發式：單向但更智能，適合單查詢。
• IDA*：迭代加深 A*，內存極小，適合嵌入式環境。
• 反向 BFS + 預計算：若多次查詢同一目標態，可預先從目標態 BFS 記錄所有狀態路徑，查詢 O(1)。