殘缺棋盤

殘缺棋盤（defective chessboard）是一個有2k×2k 個方格的棋盤，其中恰有一個方格殘缺。圖2 - 3給出k≤2時各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。注意當k= 0時，僅存在一種可能的殘缺棋盤（如圖1 4 - 3 a所示）。事實上，對于任意k，恰好存在22k 種不同的殘缺棋盤。

殘缺棋盤的問題要求用三格板（t r i o m i n o e s）覆蓋殘缺棋盤（如圖1 4 - 4所示）。在此覆蓋中，兩個三格板不能重疊，三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格。在這種限制條件下，所需要的三格板總數為( 22k -1 ) / 3。可以驗證( 22k -1 ) / 3是一個整數。k 為0的殘缺棋盤很容易被覆蓋，因為它沒有非殘缺的方格，用于覆蓋的三格板的數目為0。當k= 1時，正好存在3個非殘缺的方格，并且這三個方格可用圖1 4 - 4中的某一方向的三格板來覆蓋。

用分而治之方法可以很好地解決殘缺棋盤問題。這一方法可將覆蓋2k×2k 殘缺棋盤的問題轉化為覆蓋較小殘缺棋盤的問題。2k×2k 棋盤一個很自然的劃分方法就是將它劃分為如圖1 4 - 5 a所示的4個2k - 1×2k - 1 棋盤。注意到當完成這種劃分后， 4個小棋盤中僅僅有一個棋盤存在殘缺方格（因為原來的2k×2k 棋盤僅僅有一個殘缺方格）。首先覆蓋其中包含殘缺方格的2k - 1×2k - 1 殘缺棋盤，然后把剩下的3個小棋盤轉變為殘缺棋盤，為此將一個三格板放在由這3個小棋盤形成的角上，如圖14-5b 所示，其中原2k×2k 棋盤中的殘缺方格落入左上角的2k - 1×2k - 1 棋盤。可以采用這種分割技術遞歸地覆蓋2k×2k 殘缺棋盤。當棋盤的大小減為1×1時，遞歸過程終止。此時1×1的棋盤中僅僅包含一個方格且此方格殘缺，所以無需放置三格板。

可以將上述分而治之算法編寫成一個遞歸的C++ 函數Ti l e B o a r d (見程序1 4 - 2 )。該函數定義了一個全局的二維整數數組變量B o a r d來表示棋盤。B o a r d [ 0 ] [ 0 ]表示棋盤中左上角的方格。該函數還定義了一個全局整數變量t i l e，其初始值為0。函數的輸入參數如下：

? tr 棋盤中左上角方格所在行。

? tc 棋盤中左上角方格所在列。

? dr 殘缺方塊所在行。

? dl 殘缺方塊所在列。

? size 棋盤的行數或列數。

Ti l e B o a r d函數的調用格式為Ti l e B o a r d（0,0, dr, dc,size)，其中s i z e = 2k。覆蓋殘缺棋盤所需要的三格板數目為( s i z e2 -1 ) / 3。函數TileBoard 用整數1到( s i z e2-1 ) / 3來表示這些三格板，并用三格板的標號來標記被該三格板覆蓋的非殘缺方格。

令t (k) 為函數Ti l e B o a r d覆蓋一個2k×2k 殘缺棋盤所需要的時間。當k= 0時，s i z e等于1，覆蓋它將花費常數時間d。當k > 0時，將進行4次遞歸的函數調用，這些調用需花費的時間為4t (k-1 )。除了這些時間外， if 條件測試和覆蓋3個非殘缺方格也需要時間，假設用常數c 表示這些額外時間。可以得到以下遞歸表達式：

程序14-2 覆蓋殘缺棋盤

void TileBoard(int tr, int tc, int dr, int dc, int size)

{// 覆蓋殘缺棋盤

if (size == 1) return;

int t = tile++, // 所使用的三格板的數目

s = size/2; // 象限大小

/ /覆蓋左上象限

if (dr < tr + s && dc < tc + s)

// 殘缺方格位于本象限

Ti l e B o a r d ( t r, tc, dr, dc, s);

else {// 本象限中沒有殘缺方格

// 把三格板t 放在右下角

Board[tr + s - 1][tc + s - 1] = t;

// 覆蓋其余部分

Ti l e B o a r d ( t r, tc, tr+s-1, tc+s-1, s);}

/ /覆蓋右上象限

if (dr < tr + s && dc >= tc + s)

// 殘缺方格位于本象限

Ti l e B o a r d ( t r, tc+s, dr, dc, s);

else {// 本象限中沒有殘缺方格

// 把三格板t 放在左下角

Board[tr + s - 1][tc + s] = t;

// 覆蓋其余部分

Ti l e B o a r d ( t r, tc+s, tr+s-1, tc+s, s);}

/ /覆蓋左下象限

if (dr >= tr + s && dc < tc + s)

// 殘缺方格位于本象限

TileBoard(tr+s, tc, dr, dc, s);

else {// 把三格板t 放在右上角

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 {// 把三格板t 放在左上角

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++)

cout << setw (5) << Board[i][j];

cout << endl;

}

}

可以用迭代的方法來計算這個表達式（見例2 - 2 0），可得t (k )= ( 4k )= （所需的三格板的數目）。由于必須花費至少( 1 )的時間來放置每一塊三格表，因此不可能得到一個比分而治之算法更快的算法。