问题介绍
棋盘的完美覆盖又称多米诺覆盖(Domino Tiling)，是组合数学中一个颇有趣味的问题。首先介绍与该问题相关的一些基本概念：
- 多米诺(Domino)：一个多米诺是由两个单位正方形拼接而成的 1\times2 或 2\times1 矩形。
- 多米诺覆盖(Domino Tiling): 如果一些多米诺恰好互不重叠地覆盖一个 m\times n 棋盘，则此覆盖称为一个多米诺覆盖。
下图是 4\times4 棋盘的四种多米诺覆盖.
下面的定理回答了什么样的棋盘存在多米诺覆盖：
定理： m\times n 棋盘存在多米诺覆盖当且仅当 m 或 n 是偶数。
这一结论很容易证明：如果 m 与 n 之一为偶数(不妨设为 m)，则每一列都恰好可以被 \frac{m}2 个多米诺覆盖。反之，如果 m,n 均为奇数，则棋盘含有奇数个方格， 因而不存在多米诺覆盖。
然而，一个更具挑战性的问题是：对于给定的正整数 m,n，m\times n 棋盘共有多少种不同的多米诺覆盖？Kasteleyn 于 1961 年证明了如下结果：
定理 (Kasteleyn, 1961)： 设 m 是偶数，则 m\times n 棋盘的多米诺覆盖方法数为
Q_{m,n}=\prod_{k=1}^{\frac m2}\prod_{l=1}^n2\sqrt{\cos^2\frac{k\pi}{m+1}+\cos^2\frac{l\pi}{n+1}}
这个惊为天人的等式揭示了多米诺覆盖问题背后的秘密。例如，8\times 8 棋盘的多米诺覆盖方法数是 12988816=2^4\cdot17^2\cdot 53^2。
算法设计
下面我们将利用编程来计算多米诺覆盖的方法数。与八皇后问题类似，计算该问题使用的方法是递归回溯(而不是上面的定理)，具体说来，就是从棋盘左上角依次扫描尚未填入多米诺的小方格，然后根据方格下方和右边的空格决定下一个多米诺的摆放位置。
在存储方面，用 bool A[m][n] 存储 m\times n 棋盘，每一次加入新的多米诺时，就将相邻的一对小方格上的 bool 值设置为 1 (表示占用)。
代码实现
有了以上的准备以后，就可以用代码来实现多米诺覆盖方法数的计算了。C++代码如下：
#include <iostream>
using namespace std;
int m,n; // 长宽
bool **Chess; // 棋盘
int Count=0; // 计数
void Domino(int i,int j){
if(i==m){Count++;return;} // 完成
if(j==n-1){ // 当前方格位于最后一列
if(Chess[i][j]==0){ // 尚未放置
if(i!=m-1&&Chess[i+1][j]==0){ // 下方可以放置
Chess[i][j]=Chess[i+1][j]=1; // 放置
Domino(i+1,0); // 换行
Chess[i][j]=Chess[i+1][j]=0; // 恢复
}
}
else Domino(i+1,0); // 换行
}
else{ // 当前方格不在最后一列
if(Chess[i][j]==0){ // 尚未放置
if(i!=m-1&&Chess[i+1][j]==0){ // 下方可以放置
Chess[i][j]=Chess[i+1][j]=1; // 放置
Domino(i,j+1); // 右移
Chess[i][j]=Chess[i+1][j]=0; // 恢复
}
if(Chess[i][j+1]==0){ // 右边可以放置
Chess[i][j]=Chess[i][j+1]=1; // 放置
Domino(i,j+1); // 右移
Chess[i][j]=Chess[i][j+1]=0; // 恢复
}
}
else Domino(i,j+1); // 右移
}
}
int main(){
cin >> m >> n;
bool *p=new bool[m*n];
for(int i=0;i<m*n;i++)p[i]=0;
Chess=new bool*[m];
for(int i=0;i<m;i++)Chess[i]=p+i*n;
Domino(0,0);
cout << Count << endl;
delete []Chess;
delete []p;
return 0;
}
输入 8 8，得到的结果恰好是 12988816。
参考资料
[1] Domino Tiling: http://math.uchicago.edu/~may/REU2015/REUPapers/Borys.pdf
