盘盖问题是，在由2 k 2 k 2^{k} times 2^{k} 2k2k个撒娇者构成的盘中，如果恰好有一个撒娇者与其他撒娇者不同，则称该撒娇者为特别撒娇者。 很明显，特殊撒娇橘子出现在盘上的位置可能是4 k 4^{k} 4k。 下图为k=2 k=2 k=2时的16个特殊盘中的一个。
在柜盖问题中，除给定特殊柜的特殊撒娇外，所有撒娇都用图示的4种不同形态的LL型骨牌覆盖，任何两个L(mathrm(L ) LL型骨牌都不能重叠覆盖。 发现2 k 2 k 2^{k} times 2^{k} 2k2k中的一个棋盘的网格使用了(4k1 )/3(left(4^{k}-1 ) right )/3 )4k1 )
对于分治策略k 0 k0 k0，请访问将 2 k 2 k 2^{k} times 2^{k} 2k2k 棋盘分 割为 4 个 2 k 1 2 k 1
2^{k-1} times 2^{k-1} 2k−1×2k−1 子棋盘，如下图所示。特殊爱撒娇的橘子必位于 4 个较小子棋盘之一中，其余3 个子棋盘中无特殊爱撒娇的橘子。为了将这 3 个无特殊爱撒娇的橘子的子棋盘转化为特殊棋盘，可以用一个 L L L 型骨牌覆盖这 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("nnn"); for (i = 0; i < boardSize; i++) { for (j = 0; j < boardSize; j++) { printf("%dt", board[i][j]); } printf("nnn"); } return 0;} 时间复杂度设 T ( k ) T(k) T(k) 是算法 ChessBoard 覆盖一个 2 k × 2 k 2^{k} times 2^{k} 2k×2k 棋盘所需的时间，则从算法的分治策略可知， T ( k ) T(k) T(k) 满足如下递归方程
T ( k ) = { O ( 1 ) k = 0 4 T ( k − 1 ) + O ( 1 ) k > 0 T(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 ( 4 k ) T(k)=Oleft(4^{k}right) T(k)=O(4k) 。由于覆盖一个 2 k × 2 k 2^{k} times 2^{k} 2k×2k 棋盘所需的 L mathrm{L} L 型骨牌个数为 ( 4 k − 1 ) / 3 left(4^{k}-1right) / 3 (4k−1)/3，故算法 ChessBoard 是一个在渐近意义下最优的算法。