问题介绍

棋盘的完美覆盖又称多米诺覆盖(Domino Tiling)，是组合数学中一个颇有趣味的问题。首先介绍与该问题相关的一些基本概念：

多米诺(Domino)：一个多米诺是由两个单位正方形拼接而成的 $1\times2$ 或 $2\times1$ 矩形。
多米诺覆盖(Domino Tiling): 如果一些多米诺恰好互不重叠地覆盖一个 $m\times n$ 棋盘，则此覆盖称为一个多米诺覆盖。

下图是 $4\times4$ 棋盘的四种多米诺覆盖.

4×4 棋盘的多米诺覆盖
下面的定理回答了什么样的棋盘存在多米诺覆盖：

定理： $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。