棋盘覆盖问题

棋盘覆盖问题(chess cover problem)

在${2^k}\times {2^k}$的棋盘格($k$为正整数)中，其有1个确定位置的方格一开始是被覆盖的，现提供4种不同L型骨牌(如上图所示)。棋盘覆盖问题要求得到其中1种方案，用这4种骨牌覆盖所有方格，且覆盖是没有任何重叠的。

然后找该问题的分治算法，由于棋盘长宽相等且是2的幂，所以棋盘能拆成等大的4个象限，被覆盖的方格在某个象限里。这时考虑在中心位置选一种形状的骨牌放入1个，要求其刚好横跨另外3个没有被覆盖方格的象限。这时这4个象限每个都刚好有1个被覆盖的方格，这样就可把这4个象限当成“子棋盘”来递归的求解子问题，直到遇到$2\times 2$的“子棋盘”时，使用1个骨牌覆盖后就等于完全解决了这个子问题，而无需继续递归下去求更小规模的子问题。

由于问题的输入输出都是“棋盘”，所以用二维数组表示“棋盘”，并直接在这个数组上“覆盖”骨牌。这个程序要避免不必要的遍历，否则会导致时间复杂度变大。然后规定初始覆盖的方格用“X”填充，数组其他位置填“假”，4种骨牌分别填入ABCD的4种字母占位，这样最后打印结果时很清晰。然后构造递归函数$cover(chess,x_1,x_2,y_1,y_2,x_c,y_c)$，输入1是“棋盘”，输入2-4表示子棋盘坐标的起止位置。输入5-6表示在该子问题中，被覆盖的方格的坐标，下面是具体程序。

最后分析时间复杂度，实际的问题规模是棋盘格子数$n$，每个递归包含4个规模$\frac{1}{4}$的子递归，除子递归以外的代价只有$O(1)$，那么时间复杂度$T(n)$满足$T(n)=4T(\frac{n}{4}) + O(1)$。根据主定理直接得到$T(n)=O(n)$。