声明：凡代码问题，欢迎在评论区沟通。承蒙指正，一起成长！

一、实验内容与要求

内容：(棋盘覆盖问题)在一个2^k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
要求：随机输入k及特殊方格的坐标，并输出覆盖矩阵。

二、概要设计

1.定义整型二维数组指针全局变量，用于动态保存棋盘方格；
2.主函数中输入3个参数，分别为棋盘的规模k及特殊方格的位置x、y；
3.根据规模k为指针全局变量分配内存，并生成相应大小的全局变量数组；
4.运用算法进行棋盘覆盖：当k>0时，将2^k×2k棋盘分割为4个2^k-1×2k-1子棋盘,特殊方格必须位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题；递归地使用这种分割，直至棋盘简化为棋盘1×1。
5.输出棋盘矩阵：以-1为矩阵边框，0为特殊方格，L型骨牌的编号tile从1开始计数；在以-1为的方框中打印出2^k×2k个整型数矩阵。

三、直接上代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int tile=1;
int **board; //二维数组全局变量的指针;

void Defind_Array(int Size); //声明：为全局变量分配内存;
void ChessBoard(int tr, int tc, int dr, int dc, int siz); //声明：棋盘覆盖的函数;
void Display(int Size); //声明：打印输出函数；

int main()
{
    int k,Size,x,y; //规模,长度(Size==2^k),特殊方格位置;
    printf("规模：");
    scanf("%d",&k);
    printf("特殊方格位置下标(x,y)：");
    scanf("%d%d",&x,&y);
    Size=pow((double)2,(double)k);
    Defind_Array(Size); //定义数组;
    board[x][y]=0; //将特殊方格标记为0;
    ChessBoard(0,0,x,y,Size); //覆盖棋盘;
    Display(Size); //输出棋盘,边缘标记为-1;
    return 0;
}

void Defind_Array(int length)
{
    int p,q;
    board=(int **)malloc(length*sizeof(int *));
    for(p=0; p<length; p++)
    {
        board[p]=(int *)malloc(length*sizeof(int));
        for(q=0; q<length; q++)
            board[p][q] = p*length+q;
    }
}

void ChessBoard(int tr, int tc, int dr, int dc, int siz)
{
    int s, t1; //t1表示本次覆盖所用L型骨牌的编号
    if (siz == 1) return; //棋盘只有一个方格且是特殊方格
    t1 = tile++; // L型骨牌编号
    s = siz/2; // 划分棋盘
    if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盘中
        ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘
    else  //用 t1号L型骨牌覆盖右下角，再递归处理子棋盘
    {
        board[tr + s - 1][tc + s - 1] = t1;
        ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
    }
    if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盘中
        ChessBoard(tr, tc+s, dr, dc, s); //递归处理子棋盘
    else   //用 t1号L型骨牌覆盖左下角，再递归处理子棋盘
    {
        board[tr + s - 1][tc + s] = t1;
        ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
    }
    if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盘中
        ChessBoard(tr+s, tc, dr, dc, s); //递归处理子棋盘
    else   //用 t1号L型骨牌覆盖右上角，再递归处理子棋盘
    {
        board[tr + s][tc + s - 1] = t1;
        ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
    }
    if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盘中
        ChessBoard(tr+s, tc+s, dr, dc, s); //递归处理子棋盘
    else   //用 t1号L型骨牌覆盖左上角，再递归处理子棋盘
    {
        board[tr + s][tc + s] = t1;
        ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
    }
}

void Display(int Size)
{
    int i,j;
    for(i=0; i<Size+2; i++)
        printf("-1\t");
    printf("\n\n");
    for(i=0; i<Size; i++)
    {
        printf("-1\t");
        for(j=0; j<Size; j++)
        {
            printf("%d\t",board[i][j]);
        }
        printf("-1\t");
        printf("\n\n");
    }
    for(i=0; i<Size+2; i++)
        printf("-1\t");
    printf("\n");
}

四、运行结果

棋盘覆盖（C语言）

参考博客：https://blog.csdn.net/qq_40274351/article/details/79643213

问题描述

在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

可行性分析

2k×2k大小的棋盘，除去1个特殊位置外，一共有(4k-1)个空位置，需要用(4k-1)/3个L型骨牌来覆盖。

• (4k-1)一定能被3整除?

4k-1 = (2k)2 – 1 = (2k - 1)(2k + 1)

(2k - 1)、2k、(2k + 1)是3个连续的自然数，而2k不可能被3整除，所以(2k - 1)和(2k + 1)二者必有1个是3的倍数。

• (4k-1)个空位置必能用(4k-1)/3个L型骨牌来覆盖?

可用归纳法证明。
k = 1时： 4k-1个位置本身就是一个L型骨牌。
k = 2时：22×22大小的棋盘可以分成4个2×2大小的子棋盘，其中特殊位置位于某一个子棋盘中，用一个L型骨牌覆盖其 他3个子棋盘的会合处，则对4个子棋盘，剩余的空位置都是一个L型骨牌。

当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。

特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘k = 1。

程序实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 8
int Board[MAXSIZE][MAXSIZE];
int title=1;//全局序号

//tr：棋盘左上角方格的行号
//tc：棋盘左上角方格的列号
//dr：特殊方格所在的行号
//dc：特殊方格所在的列号
//size：size=2^k 棋盘规格为2^k*2^k
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
    if(size==1)
        return;
    int s = size/2;//分割棋盘
    int t = title++;
    //覆盖左上角子棋盘
    if(dr <tr+s && dc<tc+s) //特殊方格在此棋盘中
        ChessBoard(tr,tc,dr,dc,s);
    else//特殊方格不在棋盘中
    {
        Board[tr+s-1][tc+s-1]=t;//用t号L型骨牌覆盖右下角
        ChessBoard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格
    }
    //覆盖右上角子棋盘
    if(dr<tr+s && dc>=tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr,tc+s,dr,dc,s);
    }
    else
    {
        Board[tr+s-1][tc+s]=t;//用t号L型骨牌覆盖左下角
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格
    }
    //覆盖左下角子棋盘
    if(dr>=tr+s && dc<tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr+s,tc,dr,dc,s);
    }
    else
    {
        Board[tr+s][tc+s-1]=t;//用t号L型骨牌覆盖右上角
        ChessBoard(tr+s,tc,tr+s,tc+s-1,s);//覆盖其余方格
    }
    //覆盖右下角子棋盘
    if(dr>=tr+s && dc>=tc+s)//特殊方格在此棋盘中
    {
        ChessBoard(tr+s,tc+s,dr,dc,s);
    }
    else
    {
        Board[tr+s][tc+s] = t;//用t号L型骨牌覆盖左上角
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余方格
    }

}
int main()
{
    int i ,j;
    Board[0][1]=0;
    ChessBoard(0,0,2,3,MAXSIZE);
    for (i = 0;i<MAXSIZE;i++)
    {
        for (j=0;j<MAXSIZE;j++)
            printf("%5d",Board[i][j]);
        printf("\n");
    }
    return 0;
}

结果展示：

#include<stdio.h>
int board[100][100];
int tile=1;
void chessboard(int tr,int tc,int dr,int dc,int sizee)
{
    if(sizee==1)
       return;
    int t=tile++;
    int s=sizee/2;
    if(dr<tr+s&&dc<tc+s)
        chessboard(tr,tc,dr,dc,s);
    else
    {
        board[tr+s-1][tc+s-1]=t;
        chessboard(tr,tc,tr+s-1,tc+s-1,s);
    }
    if(dr<tr+s&&dc>=tc+s)
       chessboard(tr,tc+s,dr,dc,s);
    else
    {
        board[tr+s-1][tc+s]=t;
        chessboard(tr,tc+s,tr+s-1,tc+s,s);
    }
    if(dr>=tr+s&&dc<tc+s)
        chessboard(tr+s,tc,dr,dc,s);
    else
    {
        board[tr+s][tc+s-1]=t;
        chessboard(tr+s,tc,tr+s,tc+s-1,s);
    }
    if(dr>=tr+s&&dc>=tc+s)
        chessboard(tr+s,tc+s,dr,dc,s);
    else
    {
        board[tr+s][tc+s]=t;
        chessboard(tr+s,tc+s,tr+s,tc+s,s);
    }
}
int main()
{
    int i,j;
    board[0][1]=0;
    chessboard(0,0,0,1,4);
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
            printf("%5d",board[i][j]);
        printf("\n");
    }
    return 0;
}

思路：棋盘覆盖可以理解成找到这个特殊的方格，tr,tc分别是这个各自的左上角元素的标号，dr,dc是特殊方格的位置，tile表示用了几个骨牌了。依次划分成四个四个的区域，几个if-else语句的意思是如果特殊方格在这个区域里面就继续在这个方格里进行chessboard继续划分，如果不在这个方格里就把交接的部分，也就是左上方格把右下角涂黑，右上的把左下角涂黑，左下的把右上涂黑…然后再继续在本方格里进行划分