算法1-2：棋盘覆盖问题

★问题描述：在一个2^k×2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4^k种情形。因而对任何k≥0，有4^k种不同的特殊棋盘。在棋盘覆盖问题中，要用L型骨牌覆盖一个给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重复覆盖。

★算法设计：利用分治策略，可以设计解棋盘算法问题的一个简洁算法。

★数据输入：输入一个K值作为棋盘的大小，之后输入两个值作为特殊方格的位置

★数据输出：输出棋盘，要求标出每个L型骨牌的序号

例：

输入：

2        

2  2     

输出：

2  2  3  3

2  0  1  3

4  1  1  5

4  4  5  5

首先来分析一下，在棋盘里只有一块特殊的方格，而且棋盘的大小也比较特殊，2的K次方，非常适合切分成一半。又因为棋盘是个方形的，所以思路可以使将棋盘分成大小相同的四份。

分支法的基本思想是一个较大的问题，将其分成n个子问题，并且n个子问题解决后能合并成原问题的解。

当我们将有特殊方格的棋盘分割成4个相同的子棋盘时，4个棋盘分成两类：有特殊方格和没有特殊方格。我们用到的L型骨牌刚好是三个方格的，也就是说可以用一个L型骨牌将其余的三个没有特殊方格的棋盘变成有特殊方格的。

之后我们便可利用递归的方法来对其进行赋值。

用一个全局变量来记录用骨牌的个数，每层的骨牌序号用一个变量来记录，程序如下：

#include <stdio.h>
#include <stdlib.h>
int size;//用于记录棋盘的大小
int tile=0;//用于记录骨牌的序号
int a[128][128]={-1};
void ChessBoard(int tr,int tc,int dr,int dc,int size);
int main()
{
    int i,j,k;
    printf("请输入K值的大小：\n");
    scanf("%d",&i);
    for(j=0,k=1;j<i;j++)
        k*=2;
    printf("输入特殊方格位置：\n");
    scanf("%d%d",&i,&j);
    i--;j--;
    a[i][j]=0;
    ChessBoard(0,0,i,j,k);
    for(i=0;i<k;i++){
        for(j=0;j<k;j++)
            if(a[i][j]>9||a[i][j]==-1)
                printf(" %d",a[i][j]);
            else printf("  %d",a[i][j]);
        printf("\n");
    }
    return 0;
}
void ChessBoard(int tr,int tc,int dr,int dc,int
size){
    if(size==1)return;
    int t=++tile;//t用于保存在这一层递归中骨牌的序号
    int s=size/2;

    if(dr<tr+s&&dc<tc+s)
        ChessBoard(tr,tc,dr,dc,s);
    else {
        a[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 {
        a[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 {
        a[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 {
        a[tr+s][tc+s]=t;
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}

本文使用的代码为C语言的代码，在和同学一起讨论的过程中，发现C++中调用函数的括号可以用中括号，编译时不会显示出错，但是运行时并不会调用该函数，希望在以后使用C++编代码时可以注意一下，代码的运行结果如下：