分治算法經典應用：殘缺棋盤覆蓋問題 (三格板鋪滿 2ᵏ×2ᵏ 棋盤)

分治算法經典應用：殘缺棋盤覆蓋問題

殘缺棋盤：2ᵏ × 2ᵏ 棋盤，**恰有一格** 殘缺 (缺失)。用 **L 型三格板** (覆蓋 3 格) 完全鋪滿其餘格子，三格板不重疊、不覆蓋殘缺格。證明：需 (4ᵏ - 1)/3 塊三格板，分治算法可在 **最優時間 Θ(4ᵏ)** 內構造出鋪放方案。

分治核心思想

1. 分解：將 2ᵏ × 2ᵏ 棋盤四等分為 4 個 2ᵏ⁻¹ × 2ᵏ⁻¹ 子棋盤
2. 製造殘缺：原殘缺格落在某子棋盤 (天然殘缺)；在**中心點**放一塊三格板，覆蓋其餘 3 個子棋盤各自靠近中心的一格 → 這 3 個子棋盤**各產生一個「人工殘缺」**
3. 遞歸求解：4 個子棋盤現在**都是**標準殘缺棋盤，遞歸調用
4. 基例：k=0 (1×1) 棋盤，唯一格即殘缺，無需鋪放，直接返回

遞歸函數參數設計

void TileBoard(int tr, int tc, int dr, int dc, int size)
/*  tr, tc: 當前棋盤左上角座標 (行, 列)
    dr, dc: 殘缺格座標
    size:   當前棋盤邊長 (2ᵏ)
*/

C++ 完整實現

#include 
#include 
#include 

std::vector> Board; // 全局棋盤，0=殘缺/未覆蓋, >0=三格板編號
int tile = 1;                        // 當前三格板編號

void TileBoard(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) return; // 基例：1x1 殘缺棋盤
    
    int t = tile++;        // 本層使用的三格板編號
    int s = size / 2;      // 象限半長
    
    // === 左上象限 ===
    if (dr < tr + s && dc < tc + s) {
        // 殘缺在本象限，直接遞歸
        TileBoard(tr, tc, dr, dc, s);
    } else {
        // 製造人工殘缺：右下角
        Board[tr + s - 1][tc + s - 1] = t;
        TileBoard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    
    // === 右上象限 ===
    if (dr < tr + s && dc >= tc + s) {
        TileBoard(tr, tc + s, dr, dc, s);
    } else {
        Board[tr + s - 1][tc + s] = t; // 左下角
        TileBoard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    
    // === 左下象限 ===
    if (dr >= tr + s && dc < tc + s) {
        TileBoard(tr + s, tc, dr, dc, s);
    } else {
        Board[tr + s][tc + s - 1] = t; // 右上角
        TileBoard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    
    // === 右下象限 ===
    if (dr >= tr + s && dc >= tc + s) {
        TileBoard(tr + s, tc + s, dr, dc, s);
    } else {
        Board[tr + s][tc + s] = t; // 左上角
        TileBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

void OutputBoard(int size) {
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j)
            std::cout << std::setw(5) << Board[i][j];
        std::cout << '\n';
    }
}

int main() {
    int k = 3; // 8x8 棋盤
    int size = 1 << k;
    int dr = 2, dc = 3; // 殘缺格位置 (0-based)
    
    Board.assign(size, std::vector(size, 0));
    Board[dr][dc] = -1; // 標記殘缺格
    
    TileBoard(0, 0, dr, dc, size);
    OutputBoard(size);
    return 0;
}

複雜度分析

• 遞歸關係：T(k) = 4T(k-1) + Θ(1), T(0) = Θ(1)
• 解得：T(k) = Θ(4ᵏ) = Θ(三格板數量)
• **下界論證**︰每塊三格板至少需 Θ(1) 時間放置 → 無算法可快於 Θ(4ᵏ)

關鍵洞察

1. 問題轉化：將「一個大殘缺棋盤」轉化為「四個小殘缺棋盤」是分治的精髓 — **製造相似子問題**
2. 中心三格板：是連接四個子問題的關鍵樞紐，同時解決三個子棋盤的「非殘缺→殘缺」轉化
3. 編號機制：全局計數器 tile 為每塊三格板分配唯一 ID，便於驗證輸出與可視化

擴展變體

• 多殘缺棋盤：若允許任意偶數個殘缺格，可通過配對 + 路徑連接轉化為標準問題
• 三維擴展：2ᵏ × 2ᵏ × 2ᵏ 立方體，單位立方體缺失，用 7 體積 L 型磚塊填充
• 並行化：四個子棋盤完全獨立，天然適合多核並行 (Task Parallelism)

殘缺棋盤問題是分治算法教科書級範例，展示了「分解-製造相似子問題-遞歸求解-合併」的完整范式，其 Θ(4ᵏ) 最優複雜度證明更體現了算法下界分析的嚴謹思維。