HDU 1043 Eight 八數碼問題 BFS + 康托展開

問題描述

經典八數碼（3×3 滑塊拼圖）：給定初始狀態，求移動空格（'x'）使其變為目標狀態 12345678x 的最短移動序列（u/d/l/r）。若無解輸出 unsolvable。

核心技術：康托展開 + BFS

康托展開：排列 ↔ 整數雙向映射

將 9 元排列（含 0 代表 x）映射為 [0, 9!-1] 區間內的唯一整數，作為 BFS 訪問標記與前驅記錄的索引。

int cantor(int a[9]) {
    int code = 0;
    static const int fact[9] = {1,1,2,6,24,120,720,5040,40320};
    for (int i = 0; i < 9; ++i) {
        int cnt = 0;
        for (int j = i+1; j < 9; ++j) if (a[j] < a[i]) ++cnt;
        code += cnt * fact[8-i];
    }
    return code;
}

逆康托展開（解碼）

由整數還原排列，用於 BFS 狀態展開。

BFS 策略：從目標狀態反向搜索

1. 以目標狀態 123456780 為起點，預計算所有可達狀態的最短路徑
2. 隊列存儲康托編碼，pre[code] 記錄前驅狀態，move[code] 記錄移動方向
3. 四方向嘗試移動 0，合法則編碼新狀態，未訪問則入隊
4. 查詢時：將輸入編碼，若 vis[code]==0 輸出 unsolvable，否則回溯構建路徑

代碼框架（關鍵部分）

const int MAXS = 362880; // 9!
int pre[MAXS], mv[MAXS];
bool vis[MAXS];
int q[MAXS];

void bfs() {
    int goal[9] = {1,2,3,4,5,6,7,8,0};
    int start = cantor(goal);
    vis[start] = true; pre[start] = -1;
    int head = 0, tail = 0;
    q[tail++] = start;

    const int dx[4] = {-1,1,0,0};
    const int dy[4] = {0,0,-1,1};
    const char dir[4] = {'u','d','l','r'};

    while (head < tail) {
        int cur = q[head++];
        decode(cur, state); // 逆康托
        int z = find_zero(state);
        int r = z/3, c = z%3;
        for (int d = 0; d < 4; ++d) {
            int nr = r+dx[d], nc = c+dy[d];
            if (nr<0||nr>2||nc<0||nc>2) continue;
            swap(state[z], state[nr*3+nc]);
            int nxt = cantor(state);
            if (!vis[nxt]) {
                vis[nxt] = true;
                pre[nxt] = cur;
                mv[nxt] = d;
                q[tail++] = nxt;
            }
            swap(state[z], state[nr*3+nc]); // 復原
        }
    }
}

複雜度與優化

• 狀態空間：9! = 362,880，完全可行
• 預處理 BFS 一次，多測試案例 O(1) 回答
• 康托展開 O(9²) 可接受，亦可用查表優化至 O(9)

無解判定

八數碼可解性取決於逆序對奇偶性：初始狀態與目標狀態逆序對奇偶性相同則可解。BFS 自然覆蓋此判定（不可達狀態 vis==0）。