\(2^k\times 2^k\)棋盘覆盖问题描述如下，给出\(k\)的值，得到一块\(2^k\times 2^k\)大小的棋盘，棋盘上有一格是特殊方格。随后给出如下4种L型的骨牌，要求使用这四种L型的骨牌覆盖给定棋盘上的，除特殊方格以外的所有格子，并且任何两个L型骨牌不得重叠覆盖。
先来看\(k=1\)的情况，在这种情况下，棋盘大小为\(2\times 2\)，共4格，其中一格是特殊方格。不妨给这四格编号为\(1,2,3,4\)。如下图
显然的，此时我们有如下对应的解法
- 如果\(1\)是特殊方格，那么选择骨牌\(C\)
- 如果\(2\)是特殊方格，那么选择骨牌\(A\)
- 如果\(3\)是特殊方格，那么选择骨牌\(B\)
- 如果\(4\)是特殊方格，那么选择骨牌\(D\)
非常简单，对吧。
那么再来看\(k=2\)的时候，此时棋盘大小为\(4\times 4\)，不失一般性，我们假定它在如下图所示的位置。
虽然与\(k=1\)时的情况相比，棋盘变大了，但是若是将这个\(4\times 4\)的棋盘看作是4个\(2\times 2\)的格子所组成的大棋盘的话，那么这个特殊方格仍是在\(k=1\)的小棋盘里，而对于\(k=1\)的情况，我们已经完美解决了。在这个例子中，我们使用的是骨牌\(A\)，将它放到左上角的\(2\times 2\)的小棋盘中。这个时候，局面如下所示
看到这里，是不是觉得这和\(k=1\)时，特殊方格在\(2\)位置上的情形有些相似呢？如果我们把填上去的骨牌也看作特殊方格的话
于是我们的目标就是利用给出的\(A,B,C,D\)骨牌填好这个大一些的"L"。显然，我们可以这样的组合
相比原来给出的\(C\)骨牌大上4倍的新的L型骨牌，这里暂且叫它\(C_{@2x}\)好了。那么相对应的，我们还可以构造\(A_{@2x},B_{@2x},D_{@2x}\)。
于是对于\(k=2\)的情况，我们的策略如下，首先将这个\(4\times 4\)的棋盘看成是4个\(2\times 2\)的棋盘，然后找到特殊方格所在的那一个\(2\times 2\)棋盘，利用\(k=1\)时的知识解决。接下来，将这4个\(2\times 2\)的棋盘分别作为一个整体，使用\(A,B,C,D\)来构造\(A_{@2x},B_{@2x},C_{@2x},D_{@2x}\)。最后使用新构造的L型骨牌对应填满即可。
那么当\(k\)再大一些的时候呢。
我们有如下策略，这个\(2^k\times 2^k\)的棋盘，可以看作是4个\(2^{k-1}\times 2^{k-1}\)的棋盘，而特殊方格必在这4个小的之中，现在聚焦于特殊方格所在的那个\(2^{k-1}\times 2^{k-1}\)的棋盘。对于这个\(2^{k-1}\times 2^{k-1}\)的棋盘，它又可以看作是4个\(2^{k-2}\times 2^{k-2}\)的棋盘，特殊方格又必在这4个新的小的棋盘之中。以此类推……最终必会来到\(k=1\)的情况，而\(k=1\)的情况非常简单。接下来回到\(k=2\)，也就是4个\(2\times 2\)的棋盘的情况，这里可以利用\(A,B,C,D\)来构造\(A_{@2x},B_{@2x},C_{@2x},D_{@2x}\)解决。再下来来到\(k=3\)，也就是4个\(4\times 4\)的棋盘的情况，这里可以利用\(A_{@2x},B_{@2x},C_{@2x},D_{@2x}\)来构造\(A_{@3x},B_{@3x},C_{@3x},D_{@3x}\)解决。
以此类推，在\(k=i\)时，可以看到4个\(2^{i-1}\times 2^{i-1}\)的棋盘，然后利用\(A_{@(i-1)x},B_{@(i-1)x},C_{@(i-1)x},D_{@(i-1)x}\)来构造\(A_{@ix},B_{@ix},C_{@ix},D_{@ix}\)来解决\(k=i\)时的问题。
P.S
正好在Matrix67的博客上发现了一个有点类似的意味的文章，八皇后问题算什么，来看看无穷皇后问题吧
似乎这种解法叫做分治法。
确实是一个很不错的策略。
不过……求解更大的“L”型骨牌的摆放方式，还有一定的策略。我觉得文中的表述不够详细，可能不易于理解。在此作补充说明。
每次扩展指数k的时候，棋盘都可以划分成4个小棋盘，又可以继续划分，直至\(4^{k-1}\)个……
如果想确定其中一个最小棋盘（由4个方格构成）内的骨牌的摆放方式，需要得知该棋盘内的“特殊方格”（相当于特殊方格的一个方格），而该方格需要由比它大一个规模的棋盘来确定。
交界处的骨牌摆好之后，被骨牌占据的方格可以视为“特殊方格”。
如果比它大一个规模的棋盘中也不存在“特殊方格”，那么又需要再更大规模的棋盘中寻找“特殊方格”。
以此类推……
为了避免重复计算，应该逐级放置，首先放置四个棋盘交界处的骨牌，然后再将一个子棋盘划分成四个棋盘，继续在交界处放置骨牌，直至不可划分。（嗯……像是DP？）
这样，每个最小棋盘的“特殊方格”即可确定下来，便可求得大型L骨牌的构造方式。
这样只要给定棋盘和特殊方格就可以求出任意一个子棋盘内的骨牌摆放方式……
突然开了个脑洞……把任意彩色图像转成L型彩色骨牌组成的图案……
（好像会很好玩的样子w）
其实更像是一种mathematical approach，反正和教科书上的所谓“分治法”不一样，教科书上的“分治法”还是很暴力的，这个更像是构造性的解。
或者说是类似分形的问题，和“分治”还是不太一样，因为这里没有“（大致）相同规模的小问题”
_(:3 」∠)_似乎可以理解成先从一个很小的棋盘开始，然后放大到无限……
每次放大之后得到3个新的棋盘，然后从新棋盘的分界点开始长出一个个骨牌……直至填满……
话说，这一段……
“我们有如下策略，这个\(2^k\times 2^k\)的棋盘，可以看作是4个\(2^{k-1}\times 2^{k-1}\)的棋盘，而特殊方格必在这4个小的之中，现在聚焦于特殊方格所在的那个\(2^{k-1}\times 2^{k-1}\)的棋盘。对于这个\(2^{k-1}\times 2^{k-1}\)的棋盘，它又可以可以看作是4个\(2^{k-2}\times 2^{k-2}\)的棋盘，特殊方格又必在这4个新的小的棋盘之中。以此类推……最终必会来到\(k=1\)的情况，而\(k=1\)的情况非常简单。”
Σ( ° △ °|||)︴总觉得就是分治法的思想的样子……
想象中，大概是扩展出的三个新棋盘上分别运用了分治法求解……
分治法的话，
1. divide (to subproblems)
2. conquer (each one of the "smallest" subproblem)
3. merge (results from all subproblems)
这里要用算法实现的话，实际上不需要划分子问题，因为\(k\)是可以直接拿到的，特殊方格的位置也是直接知道的，然后用代数就可以直接解了。
所以这边分治法的3个最明显的特征其实都应该说是没有的，构造更大的L骨牌的时候，可以直接对四种情况打表（将骨牌抽象，把在\(k=i-1\)时组合之后的看成一个整体，用于\(k=i\)时构造新的L骨牌）
不如说用递归（再结合尾递归优化）来实现会更好。
居然可以对四种情况打表……
_(:3 」∠)_果然我还是太弱了
_(:3 」∠)_这么说确实很像分形
(/・ω・＼)于是这算法比我想象中还要巧妙……
人工构造四种更大的L型骨牌
递归查表得到尺寸翻倍的骨牌
一层层套上去
得到解
第一块L型骨牌的角度好像只需要对特殊方块的x和y分别模2就能求得的样子……
（想写着玩一玩）
用代码写的话，毕竟因为形状是L型的，所以不太方便地方就是记录每一个L的结构。。而且\(k\)一大起来的话，可视化所占用的资源也不少，即使用像素来做，\(k\)大概10~20之后所占用的内存资源也是相当可观的了……
绘图当然也可以按照这个算法来做w
骨牌总是L型的，而且只有4种旋转角度，那么可以把棋盘上的格子之间的点作为坐标，骨牌放置于点上。
所以要表示一个骨牌，只需要这样的信息：
1.x和y坐标
2.骨牌的大小（四个小骨牌拼成一个大骨牌）
那么，对于\(2^{k}*2^{k}\)的棋盘
只需要这样的k条记录就可以表示整个棋盘的局面了。
16×16的棋盘只需要4条记录诶！
绘图的话……
为了方便表述，下文把最小的骨牌叫做1阶骨牌，由4个1阶骨牌拼接成的大L叫做2阶骨牌，4个2阶骨牌拼接成的更大的L叫做3阶骨牌……如此循环k次，叫做k阶骨牌。
如果记录按骨牌大小升序排序，那么，第n条记录所表示的骨牌为k阶……
构造k阶骨牌的图形，需要k-1阶骨牌。
于是可以从1阶骨牌开始绘图，得到一个最基本的L图形；
旋转拼接得到2阶骨牌，存储为一个2阶骨牌图形；
用2阶骨牌图形进行同样的旋转拼接得到了3阶骨牌图形；
……
然后摆放到对应的坐标，旋转成指定角度，得到整个棋盘的图形。