分治（详解残缺棋盘 —— Java代码实现）

divide-and-conquer(P) {
	if (|P| <= n0) abhoc(P);  // 解决小规模的问题
	divide P into smaller subinstances P1, P2 ,... ,Pk  // 分解问题
	for (i = 1; i <= k; i++) {
		yi = divide-and-conquer(Pi);  // 递归的解各子问题
		return merge(y1, ... ,yk)  // 将各子问题的解合并为原问题的解
	}
}

package Chess;

public class Chess {
	// 表示棋盘
	private int[][] board;
	// 表示棋盘的大小为2的多少次方
	private int boardSize;
	// 棋盘中特殊方格的位置（行号，列号）
	private int dr, dc;
	private int tile = 1;
	
	public Chess() {
		board = new int[1][1];
		dr = 0;
		dc = 0;
		boardSize = 0;
	}
	
	public Chess(int r, int c, int s) {
		int n;
		n = (int) Math.pow(2, s);
		if (n <= r || n <= c)
			System.out.println("初始化参数错误！");
		else {
			board = new int[n][n];
			dr = r;
			dc = c;
			boardSize = s;
		}
	}
	
	public void Print() {
		for (int i = 0; i < Math.pow(2, this.boardSize); i++) {
			for (int j = 0; j < Math.pow(2, this.boardSize); j++) {
				System.out.printf("%3d|", this.board[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		// 2^2*2^2棋盘, 假设特殊方格位置为（3, 3）
		Chess c1 = new Chess(3, 3, 2);
		c1.chessBoard(0, 0, c1.dr, c1.dc, (int)Math.pow(2, c1.boardSize));
		c1.Print();
	}
	
	
	/**
	 * @param tr：棋盘左上角方格的行号
	 * @param tc：棋盘左上角方格的列号
	 * @param dr：特殊方格所在的行号
	 * @param dc：特殊棋盘所在的列号
	 * @param size：2^k, 棋盘的规格为 2^k*2^k
	 **/
	public void chessBoard(int tr, int tc, int dr, int dc, int size) {
		if (size == 1) return;
		
		// t: L型骨牌号，s分割棋盘
		int t = tile++;
		int s = size / 2;
		
		// 覆盖左上角棋盘
		if (dr < tr + s && dc < tc + s) {
			// 特殊方格在此棋盘中
			chessBoard(tr, tc, dr, dc, s);
		} else { 
			// 此棋盘中无特殊方格则用t号L型骨牌覆盖右下角
			board[tr + s - 1][tc + s - 1] = t;
			// 覆盖其余方格
			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 {
			// 无特殊方格，用t号骨牌覆盖左下角
			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 {
			// 无特殊方格，用t号骨牌覆盖右上角
			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 {
			// 无特殊方格，用t号骨牌覆盖左上角
			board[tr + s][tc + s] = t;
			chessBoard(tr + s, tc + s, tr + s, tc + s, s);
		}
	}
}

  2|  2|  3|  3|

  2|  1|  1|  3|

  4|  1|  5|  5|

  4|  4|  5|  0|