注意到4*4区域中，旋转毯子1可以使空白位置处于右下角4个格子任意位置，则可以旋转4*4大正方形加上旋转毯子1，使空白处于4*4中任意位置，而4*4又是8*8的1/4，所以也能通过旋转使空白处于8*8的任意位置

经典分治法

边长为2的幂就有一种通用的构造法，但边长为5或7就不是随便一个位置都有解了。

洛谷P1228

花点时间写了个程序跑了下

把那个111地毯换成222不就行了吗，

如果地毯是n×n大小的，且n不为3的倍数，那还有解吗？

为什么把计算机的题丢在数学吧。。
用分治法，如图，将地图均分为4等份，然后铺一块L块在中间使得地图每一份均有一个格子被占，则问题被分为更小的四个子问题，然后递归考虑这四份即可。

我直接枚举法

经典分治法，属于简单题，想出来就很好做

我不是学计算机的，对这类密铺问题的了解仅限一个X算法（还是正好到自己的研究方向才了解到的），一开始错误估计了这类问题用X算法的计算量，写了程序结果跑了几个小时都跑不出来解。今天上午按楼上的说法用分治法简化了问题，于是很快就得到了题目问题的一个解：

事实上，就像楼上所说的，“公主”站在哪里对这个8*8地块的问题没有任何影响。经过分治法简化后，即使是公主站在(4,4)的格子，也能很快得到一个解：

公主站在哪里对该问题并没有任何影响。分治法给这个问题引入了非常强的先验，所以让X算法这种启发式算法“有了方向”。

精确覆盖问题可以用DLX算法

有点想法，但是不多
假设有两个2x2的正方形重叠，有一格共享，如下
011
111
110
那么显而易见，只要正方形内其中一个格子确定为空，有且只有一种摆放方式
我们拓展这个方法，如果有三个正方形两两重叠，那么只要有一个格子确定为空，其他三个正方形内的摆放方式就确定了
将这个定理拓展至2nx2n的正方形，底部铺满2x2的方格，只要在上层铺设额外的方块令每个方块存在两两重叠即可
不知道这个方向能不能证