一、问题描述
残缺棋盘游戏问题
所谓残缺棋盘是指有一个格子残缺的棋盘。例如：
所谓三格板是指缺一个格子的 2*2 的棋盘。例如：
给定一个 2
n
*2
n
的残缺棋盘，问如何放置三格板，使得除残缺格外，棋盘中其
他格子都被三格板覆盖，并且放置的三格板互不重叠。
例如：
二、算法设计
用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖 2
n
*2
n
残
缺棋盘的问题转化为覆盖较小残缺棋盘的问题。2
n
*2
n
棋盘一个很自然的划分方
法就是将它划分为 4 个 2
n-1
*2
n-1
棋盘。当完成这种划分后，V4 个小棋盘中仅仅有
一个棋盘存在残缺方格。首先覆盖其中包含残缺方格的 2
n-1
*2
n-1
残缺棋盘，然后
把剩下的 3 个小棋盘转变为残缺棋盘，为此将一个三格板放在由这 3 个小棋盘
形成的角上。可以采用这种分割技术递归地覆盖 2
n
*2
n
残缺棋盘。当棋盘的大小
减为 1×1 时，递归过程终止。此时 1×1 的棋盘中仅仅包含一个方格且此方格残
缺，所以无需放置三格板。
可以将上述分而治之算法编写成一个递归的 C++ 函数 Ti l e B o a r d。该函数
定义了一个全局的二维整数数组变量 B o a r d 来表示棋盘。B o a r d [ 0 ] [ 0 ]表
示棋盘中左上角的方格。该函数还定义了一个全局整数变量 t i l e，表示所使用
的三格板的数目，其初始值为 0。函数的输入参数如下：
tr 棋盘中左上角方格所在行。
tc 棋盘中左上角方格所在列。
dr 残缺方块所在行。
dl 残缺方块所在列。
size 棋盘的行数或列数。
