棋盘覆盖问题
在一个 2k×2k2^{k} \times 2^{k}2k×2k 个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为特殊方格。显然，特殊方格在棋盘上出现的位置有 4k4^{k}4k 种情形。下图是 k=2k=2k=2 时 16 个特殊棋盘中的一个。
在棋盘覆盖问题中，要用图示的 4 种不同形态的 LLL 型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2 个 L\mathrm{L}L 型骨牌不得重叠覆盖。易知，在任何一个 2k×2k2^{k} \times 2^{k}2k×2k 的棋盘覆盖中，用到的 LLL 型骨牌个数恰为 (4k−1)/3\left(4^{k}-1\right) / 3(4k−1)/3 。
分治策略
当 k>0k>0k>0 时，将 2k×2k2^{k} \times 2^{k}2k×2k 棋盘分 割为 4 个 2k−1×2k−12^{k-1} \times 2^{k-1}2k−1×2k−1 子棋盘，如下图所示。特殊方格必位于 4 个较小子棋盘之一中，其余3 个子棋盘中无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，可以用一个 LLL 型骨牌覆盖这 3 个小棋盘的回合处。由此，问题转化成了 4 个规模较小的棋盘覆盖问题。
伪代码
C++代码
#include <iostream>int tile = 1; // 骨牌序号int board[128][128]; // 二维数组模拟棋盘// (tr,tc)表示棋盘的左上角坐标(即确定棋盘位置), (dr,dc)表示特殊方块的位置, size=2^k确定棋盘大小void chessBoard(int tr, int tc, int dr, int dc, int size){// 递归出口if (size == 1)return;int s = size / 2; //分割棋盘int t = tile++; //t记录本层骨牌序号// 判断特殊方格在不在左上棋盘if (dr < tr + s && dc < tc + s){chessBoard(tr, tc, dr, dc, s); //特殊方格在左上棋盘的递归处理方法}else{board[tr + s - 1][tc + s - 1] = t; // 用t号的L型骨牌覆盖右下角chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); // 递归覆盖其余方格}// 判断特殊方格在不在右上棋盘if (dr < tr + s && dc >= tc + s){chessBoard(tr, tc + s, dr, dc, s);}else{board[tr + s - 1][tc + s] = t;chessBoard(tr, tc + s, tr + s - 1, tc + s, s);}// 判断特殊方格在不在左下棋盘if (dr >= tr + s && dc < tc + s){chessBoard(tr + s, tc, dr, dc, s);}else{board[tr + s][tc + s - 1] = t;chessBoard(tr + s, tc, tr + s, tc + s - 1, s);}// 判断特殊方格在不在右下棋盘if (dr >= tr + s && dc >= tc + s){chessBoard(tr + s, tc + s, dr, dc, s);}else{board[tr + s][tc + s] = t;chessBoard(tr + s, tc + s, tr + s, tc + s, s);}}int main(){int boardSize = 8; // 棋盘边长chessBoard(0, 0, 3, 3, boardSize); // (0, 0)为顶点，大小为boardSize的棋盘； 特殊方块位于(3, 3)// 打印棋盘int i, j;printf("\n\n\n");for (i = 0; i < boardSize; i++){for (j = 0; j < boardSize; j++){printf("%d\t", board[i][j]);}printf("\n\n\n");}return 0;}
时间复杂度
设 T(k)T(k)T(k) 是算法 ChessBoard 覆盖一个 2k×2k2^{k} \times 2^{k}2k×2k 棋盘所需的时间，则从算法的分治策略可知， T(k)T(k)T(k) 满足如下递归方程
T(k)={O(1)k=04T(k−1)+O(1)k>0T(k)=\left\{\begin{array}{ll} O(1) & k=0 \\ 4 T(k-1)+O(1) & k>0 \end{array}\right. T(k)={O(1)4T(k−1)+O(1)k=0k>0
解此递归方程可得 T(k)=O(4k)T(k)=O\left(4^{k}\right)T(k)=O(4k) 。由于覆盖一个 2k×2k2^{k} \times 2^{k}2k×2k 棋盘所需的 L\mathrm{L}L 型骨牌个数为 (4k−1)/3\left(4^{k}-1\right) / 3(4k−1)/3，故算法 ChessBoard 是一个在渐近意义下最优的算法。
