用四种方法实现棋盘覆盖问题加上C语言代码

棋盘覆盖问题是指在一个 $2^n \times 2^n$ 的棋盘上，恰好有一个方格是缺失的，用 L 形骨牌覆盖每个方格，使得每个 L 形骨牌恰好覆盖三个方格，要求图案连通且不重叠。下面介绍四种具体实现方法：

方法一：分治法

这是一种自顶向下的递归方法，假设缺失的方格在左上角，将棋盘分成四个 $2^{n-1}\times 2^{n-1}$ 的子棋盘，缺失的方格必定在其中一个子棋盘中，用一块 L 形骨牌填补这个子棋盘中心的空格。然后递归地处理另外三个子棋盘。

用 C 语言实现步骤如下：

void chessboard_covering(int n, int x0, int y0, int x, int y, int (*A)[MAXN]) {
    if (n == 1) return;
    int t = ++tile;
    int m = n / 2;
    if (x < x0 + m && y < y0 + m)
        chessboard_covering(m, x0, y0, x, y, A);
    else {
        A[x0+m-1][y0+m-1] = t;
        chessboard_covering(m, x0, y0, x, y, A);
    }
    if (x < x0 + m && y >= y0 + m)
        chessboard_covering(m, x0, y0+m, x, y, A);
    else {
        A[x0+m-1][y0+m] = t;
        chessboard_covering(m, x0, y0+m, x, y, A);
    }
    if (x >= x0 + m && y < y0 + m)
        chessboard_covering(m, x0+m, y0, x, y, A);
    else {
        A[x0+m][y0+m-1] = t;
        chessboard_covering(m, x0+m, y0, x, y, A);
    }
    if (x >= x0 + m && y >= y0 + m)
        chessboard_covering(m, x0+m, y0+m, x, y, A);
    else {
        A[x0+m][y0+m] = t;
        chessboard_covering(m, x0+m, y0+m, x, y, A);
    }
}

方法二：随机化算法

这种方法直接随机选取一块 L 形骨牌覆盖一个空白格子，并将相邻的格子涂成另外两个颜色，然后递归处理。选取骨牌和涂色方案是随机的，一般情况下需要多次尝试才能得到正确的结果。

方法三：DLX算法

DLX（Dancing Links X）算法是一种高效的搜索算法，可用于解决精确覆盖问题。将棋盘的每个方格和骨牌都看成一个节点，在节点间建立一个十字链表，每种骨牌对应的节点连成一个环。将缺失的格子看成一个特殊的列，将其与能够覆盖它的骨牌所对应的行连成一个环。然后从十字链表中依次选择骨牌进行覆盖，并删去相应的列和行。如果成功地删掉了所有列，那么算法结束，否则回溯。

方法四：Z 形法

该算法也称为预处理法，是一种面向具体问题的优化方法。通过对特定规模下的棋盘的覆盖情况进行预处理，然后通过查表的形式得到结果，省去构造和搜索的过程。

用 C 语言实现棋盘覆盖问题的 Z 形法步骤如下：

const int MAXN = 1024;
int A[MAXN][MAXN];
void init() {
    int m = 1, n = 1, t = 0;
    A[0][0] = A[0][1] = A[1][0] = 1; A[1][1]=++t;
    while (m < n || m < MAXN && n < MAXN) {
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j) {
                A[n+j][m+i] = A[j][i] + t * m * m;
                A[m+j][n+m-i-1] = A[j][i] + t * m * m * 2;
                A[n+m-i-1][n+m-j-1] = A[j][i] + t * m * m * 3;
            }
        m *= 2, n += m, t = A[m-1][m-1];
    }
}
int main() {
    init();
    int n;
    while (scanf("%d", &n) == 1) {
        int m = 1;
        while (m < n) m *= 2;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j)
                printf("%3d", A[i][j] < n*n ? A[i][j] : -1);
            printf("\n");
        }
    }
    return 0;
}

注意事项：表格难以在markdown中结构化，如需查看代码，可在其他编译器中编译。