POJ 1077 八數碼：BFS + 康托展開求最短移動序列

問題描述

3×3 八數碼問題：初始狀態到目標狀態 123456780（0 代表空格）。每步移動空格與相鄰數字交換。求最短移動序列（輸出操作字符 u/d/l/r），無解輸出 unsolvable。單測試案例（POJ）或多案例（HDU）。

核心技術：康托展開狀態壓縮

將 9 位排列映射為 [0, 9!-1] 的整數：

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

用於 visited 數組索引、去重、路徑回溯。

BFS 流程

1. 初始狀態入隊，visited[rank]=true，dist[rank]=0，pre[rank] 存儲前驅狀態（或存儲完整棋盤用於回溯）。
2. 彈出狀態，找 0 位置，嘗試 4 方向移動。
3. 生成新狀態，計算 newRank，若未訪問則入隊，記錄前驅與操作。
4. 到達目標狀態，回溯輸出路徑。

路徑回溯技巧

存儲每個狀態的完整棋盤 state[rank][9]（空間 9! * 9 ≈ 3.2M 字節，可接受）。回溯時：從目標狀態反向，找到空格位置，嘗試反向移動，檢查前驅狀態的 dist 是否比當前少 1 且已訪問，確定操作字符。

參考代碼片段 (關鍵部分)

int factorial[10];
void initFact() { factorial[0]=1; for(int i=1;i<10;++i) factorial[i]=factorial[i-1]*i; }

int cantor(int *a) {
    int rank = 0;
    for (int i = 0; i < 9; ++i) {
        int cnt = 0;
        for (int j = i+1; j < 9; ++j) if (a[j] < a[i]) ++cnt;
        rank += cnt * factorial[8-i];
    }
    return rank;
}

// BFS 主循環略
// 回溯輸出
void printPath(int startRank, int goalRank) {
    if (startRank == goalRank) return;
    int cur[9]; memcpy(cur, state[goalRank], sizeof(cur));
    int zeroPos = find(cur, cur+9, 0) - cur;
    for (int d = 0; d < 4; ++d) {
        int nz = zeroPos + dx[d], ny = zeroPos + dy[d]; // 反向移動
        if (valid) {
            swap(cur[zeroPos], cur[nz]);
            int pr = cantor(cur);
            if (dist[pr] + 1 == dist[goalRank] && visited[pr]) {
                printPath(startRank, pr);
                putchar(dirChar[d]); // 對應反向操作
                return;
            }
            swap(cur[zeroPos], cur[nz]); // 復原
        }
    }
}

多測試案例優化

• HDU 多案例需重置 visited/dist/state，用 memset 或 vector 重建。
• 目標狀態固定，可預計算 goalRank。
• 雙向 BFS 可大幅加速，但單向 BFS 在 9! 狀態空間下通常也能過（POJ 單案例）。

複雜度

狀態空間 9! = 362880。BFS 時間空間均 O(9!)，C++ 約 0.5s 內完成。

總結

• 八數碼是狀態空間搜索經典例題，康托展開是排列去重標準技巧。
• 路徑回溯存儲完整狀態雖佔內存但編碼簡單，避免存儲操作字符的複雜性。
• 注意輸入格式：字符串含 x 代表 0，可能有空格/換行，用 gets 或逐字符讀取。