HDU 2918 Tobo or not Tobo：IDA* 搜索還原 3×3 旋轉拼圖

遊戲規則

3×3 棋盤，數字 1-9。四個旋鈕 A,B,C,D，每個旋鈕旋轉 90° 影響周圍 4 個格子。給定打亂後狀態，限制步數 Y，求最少步數還原到標準狀態（123/456/789），超過 Y 輸出 -1。

IDA* 算法

迭代加深 A*：f = g + h，g 為當前步數，h 為啟發式估值。若 f > limit 剪枝，逐層加深 limit 直到找到解。

啟發式函數：曼哈頓距離和

每個數字到目標位置的曼哈頓距離之和。一次旋轉最多改變 4 個格子位置，每個格子移動 1 步，所以 h = ceil(sum/4) 可接受。

剪枝策略

• 不撤銷上一步：記錄上一步旋鈕和方向，下一步不反向操作。
• 限制深度不超過輸入 Y。

代碼框架

int dir[4][4] = {{3,0,4,1},{4,1,5,2},{6,3,7,4},{7,4,8,5}}; // 旋鈕影響的格子索引
int h(int a[3][3]) {
    int sum = 0;
    for (int i=0;i<3;++i) for (int j=0;j<3;++j)
        sum += abs(i - (a[i][j]-1)/3) + abs(j - (a[i][j]-1)%3);
    return (sum + 3) / 4;
}

bool dfs(int dep, int a[3][3], int lastDial, int lastDir) {
    int est = h(a);
    if (dep + est > limit) return false;
    if (est == 0) return true;
    for (int dial=0; dial<4; ++dial) {
        if (dial == lastDial) continue; // 簡化：不連續同旋鈕
        for (int dir=-1; dir<=1; dir+=2) { // 順/逆時針
            rotate(a, dial, dir);
            if (dfs(dep+1, a, dial, dir)) return true;
            rotate(a, dial, -dir); // 回溯
        }
    }
    return false;
}

複雜度

狀態空間 9! = 362880，IDA* 配合曼哈頓距離剪枝極快，Y≤30 即可解決。