一、问题描述
在一个2k×2 k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。 棋盘覆盖问题要求用图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
二、问题分析
首先，从最简单的情况开始考虑，如果只是一个2x2的棋盘，那么肯定是有解的，因为这就是最基本的情况。
但是当n很大的时候，该问题还有解吗？这是我们需要考虑的问题。
这个我们可以利用数学归纳法来证明：
假设当n = k的时候该问题有解，那么如何证明当n = k + 1的时候也有解呢？
证明过程如下：
我们可以n = k + 1的棋盘的正中央的2x2的方格中放置一个L型骨牌，使得剩下的三个子棋盘都具有自己的特殊方格。
那么此时该问题就被划分成了四个子问题。
而根据假设：当n = k的时候该问题有解。
所以当n = k + 1的时候，也相应有解。
三、数据结构设计
经过上述的分析之后，我们就可以利用分治的方法来解决这个问题。
通过上述分析我们即可知道，在分治的过程中，遇到子棋盘没有特殊方格的时候，我们就给予这个棋盘的父棋盘中心点处给予一个特殊方格，从而三个组合在一起就是一个完整的L型骨牌。
那么我们就可以进行数据结构的设计了：
如下图所示：
四、算法设计
五、代码分析
观察上述代码可以发现，算法的整个部分采用了四个递归，分成了四种情况：
特殊方格在第1象限特殊方格在第2象限特殊方格在第3象限特殊方格在第4象限
如果特殊方格在第二象限，就继续对第二象限进行划分，直到划分为4个1x1的小方格。
当划分到没有特殊方格的时候，就需要补方格了。
这时要注意，每一层的递归，L型骨牌的数量也要随之递增。
而当第二象限被填满的时候，递归就要往回走了。一直走到最开始的第一层函数调用，开始走第二个if判断，发现第一象限没有特殊方格，因此给第一象限的左下角补上一个特殊方格，然后开始在第一象限内调用递归函数，以此类推…
过程如下图所示：
如果觉得《「分治法」棋盘覆盖问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
