l型骨牌的个数是

（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；

（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；

（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;

（4） L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。

设全局变量t已初始化为0，分治法求解棋盘覆盖问题的算法用C++语言描述如下：

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

{

int s, t1; //t1表示本次覆盖所用L型骨牌的编号

if (size == 1) return; //棋盘只有一个方格且是特殊方格

t1 = ++t; // L型骨牌编号

s = size/2; // 划分棋盘

if (dr< tr + s && dc< tc + s) //特殊方格在左上角子棋盘中

ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘

else{ //用 t1号L型骨牌覆盖右下角，再递归处理子棋盘

board[tr + s - 1][tc + s - 1] = t1;

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 { //用 t1号L型骨牌覆盖左下角，再递归处理子棋盘

board[tr + s - 1][tc + s] = t1;

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 { //用 t1号L型骨牌覆盖右上角，再递归处理子棋盘

board[tr + s][tc + s - 1] = t1;

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 { //用 t1号L型骨牌覆盖左上角，再递归处理子棋盘

board[tr + s][tc + s] = t1;

ChessBoard(tr+s, tc+s, tr+s, tc+s, s);