殘缺棋盤（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 )的時間來放置每一塊三格表，因此不可能得到一個比分而治之算法更快的算法。
