问题
一个
的棋盘里有一个格子为特殊方格，现使用占3个格子的L型骨牌（方向任意）填满除特殊方格外的所有格子，问填满一个
分治策略
试验得知摆放的策略为：将整体的棋盘四等分为4个块，将L型骨牌摆放至四等分的交界处，缺口对应着含有特殊方块的那一个大块，以此规律细分下去就能填满方块（见图）。
1.png
被填上的格子（L骨牌占的格子）又会被作为新的“特殊方块”进行接下来的：分成四块，填没有特殊格的三个方块，分成四块，填方块...
因此可以得到分治与递归的策略如下：
2.png
-
为什么会固定填充？
- 如果不在某块里，它必定与其他两块一起被一个小L骨牌覆盖。不论特殊方块在哪个大块里，其余的大块的填充位置都集中在中心，可以唯一确定
-
“作为一整块”递归的问题：如何递归传递块的位置参数？
可以选择块的左上角的坐标为定位点，传入最开始的左上角坐标作为定位点
，传入整块的大小
。分割后块的长宽变为
。通过
的运算来找到点的位置，如下图所示
- 3.png
-
各点坐标如下：
- 左上角块：起始点
(tr,tc)填充点(tr+s-1,tc+s-1) - 右上角块：起始点
(tr+s,tc)填充点(tr+s,tc+s-1) - 左下角块：起始点
(tr,tc+s)填充点(tr+s-1,tc+s) - 右下角块：起始点
(tr+s,tc+s)填充点(tr+s, tc+s)
- 左上角块：起始点
伪代码
chessBoard(tr, tc, dr, dc, size) # 传入起点坐标 特殊方格坐标 棋盘大小
if (大小为1)
return
t = ++tile # 骨牌号
s = size / 2 # 分隔后的大小
if (特殊点在左上格)
chessBoard(tr, tc, dr, dc, s) # 起始点不变 特殊点不变
else # 没在左上格里就填充右下
board(右下) = t
chessboard(tr, tc, tr+s-1, tc+s-1, s) # 特殊点坐标为右下角坐标
if (特殊点在右上格)
chessBoard(tr+s, tc, dr, dc, s) # 起始点改变为右上起始点 特殊点不变
else # 没在右上格里就填充左下
board(左下) = t
chessboard(tr+s, tc, tr+s, tc+s-1, s) # 起始点变右上块起始坐标，特殊点坐标为左下角坐标
if (特殊点在左下格)
chessBoard(tr, tc+s, dr, dc, s) # 起始点不变 特殊点不变
else # 没在左下格里就填充右上
board(右上) = t
chessboard(tr, tc+s, tr+s-1, tc+s, s) # 特殊点坐标为右上角坐标
if (特殊点在右下格)
chessBoard(tr+s,tc+s, dr, dc, s) # 起始点右下 特殊点不变
else # 没在右下格里就填充左上
board(左上) = t
chessboard(tr+s, tc+s, tr+s, tc+s, s) # 特殊点坐标为左上角坐标
