棋盘覆盖问题（Java）
1、问题描述
在一个2k×2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。显然特殊方格在棋盘上出现的位置有4k 种情形.因而对任何 k ≥ 0 ,有4k种不同的特殊棋盘。如下图中的特殊棋盘是当 k = 2 时16个特殊棋盘中的一个。
在棋盘覆盖问题中,要用下图所示的4种不同形态的 L型 骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。易知，在任何一个2k×2k的棋盘覆盖中，用到的L型骨牌个数恰好为(4k - 1)/3。
2、算法设计思路
使用分治策略，可以设计出解棋盘覆盖问题的简洁算法。
当 k>0 时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘，如下图(a)所示。
特殊方格必位于4个 较小子棋盘之一 中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的 会合处 ，如下图(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。 递归 地使用这种分割，直至棋盘简化为棋盘 1×1 。
3、代码实现
特殊棋盘我们采用0来表示，同时假设特殊方格的位置为第三行第三列
棋盘一分为四之后，依次覆盖左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘。如若特殊方格在子棋盘中，则递归执行该子棋盘的操作；若不在，对于左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘而言，用编号为t的L型骨牌依次覆盖右下角、左下角、右上角、左上角的方格。
/
/*** TODO 棋盘覆盖算法 特殊棋盘我们采用0来表示**/publicclasschessBoard { staticfinalintSIZE=4; staticint[][] board=newint[SIZE][SIZE]; staticinttitle=1; // title表示L型骨牌的编号publicstaticvoidmain(String[] args) { // TODO 假设特殊方格的位置为第三行第三列board[2][2] =0; ChessBoard(0, 0, 2, 2, SIZE); System.out.println(SIZE+"*"+SIZE+"的L型骨牌棋盘为："); for (inti=0; i<SIZE; ++i) { for (intj=0; j<SIZE; j++) { System.out.print(board[i][j] +" "); } System.out.println(); } } /**** @param tr 表示棋盘左上角行号* @param tc 表示棋盘左上角列号* @param dr 表示特殊棋盘的行号* @param dc 表示特殊棋盘的列号* @param size =2^k。棋盘的规格为2^k*2^k*/publicstaticvoidChessBoard(inttr, inttc, intdr, intdc, intsize) { if (size==1) { return; } intt=title++; // t表示L型骨牌的编号ints=size/2; // 分割的子棋盘的规格大小（切分为4个子棋盘）// TODO 1.覆盖左上角子棋盘if (dr<tr+s&&dc<tc+s) { // TODO 说明特殊方格在此子棋盘中ChessBoard(tr, tc, dr, dc, s); } else { // TODO 说明特殊方格不在此子棋盘中// 用t号L型棋盘覆盖这个子棋盘的右下角board[tr+s-1][tc+s-1] =t; // TODO 覆盖其余棋盘方格ChessBoard(tr, tc, tr+s-1, tc+s-1, s); } // TODO 2.覆盖右上角子棋盘if (dr<tr+s&&dc>=tc+s) { ChessBoard(tr, tc+s, dr, dc, s); } else { // 用t号L型棋盘覆盖这个子棋盘的左下角board[tr+s-1][tc+s] =t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); } // TODO 3.覆盖左下角子棋盘if (dr>=tr+s&&dc<tc+s) { ChessBoard(tr+s, tc, dr, dc, s); } else { // 用t号L型棋盘覆盖这个子棋盘的右上角board[tr+s][tc+s-1] =t; ChessBoard(tr+s, tc, tr+s, tc+s-1, s); } // TODO 4.覆盖右下角子棋盘if (dr>=tr+s&&dc>=tc+s) { ChessBoard(tr+s, tc+s, dr, dc, s); } else { // // 用t号L型棋盘覆盖这个子棋盘的左上角board[tr+s][tc+s] =t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); } } }
4、复杂度分析
设T(k)是算法chessBoard覆盖一个2k×2k棋盘所需的时间。从算法的分隔策略可以知道，T(k)满足以下的递归方程：
- 当k = 0时，T(k) = O(1),
- 当k > 0时，T(k) = 4T(k - 1) + O(1)
最终此递归方程可得：T(n) = O(4k)。
由于覆盖2k×2k棋盘所需的L型骨牌个数为(4k - 1)/3，所以此算法是一个在渐进意义下的最优算法。
5、参考
- 算法分析与设计（第四版）
