学步园

引言
      在<<算法系列---回溯算法>>一节,讨论回溯算法及其应用,回溯能够在可以接受的时间内解决某些规模的组合问题,这节再讨论它的一个非常有意思的应用---跳马问题(骑士周游问题)。

问题
跳马问题也称为骑士周游问题，是算法设计中的经典问题。其一般的问题描述是：

     考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马的周游路线。

此题实际上是一个Hamilton回路问题,和迷宫问题很相似,可以用回溯算法来解决.
考虑到马在每一个位置,最多有8种跳法,如下图所示:
 

		K7		K0
	K6				K1
			K
	K5				K2
		K4		K3

可以使用N皇后问题的算法模板。
算法如下：

#include <stdio.h>
#include <stdlib.h>
/**//**/
//棋盘行数
const int N = 8;

int step[N * N] = {-1}; //保存每一步做出的选择
int chess[N][N] = {0}; //棋盘
//下一个方向
int Jump[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

int p = 0;//对解的个数计数

//判断是否合法
int canJump(int x, int y)
{
    if (x >= 0 && x < N && y >= 0 && y < N && chess[x][y] == 0)
        return 1;
    return 0;
}
//输出结果
void OutPutChess()
{
    int i;
    for (i = 1; i <= N * N - 1; ++i)
        {
            printf("%d ", step[i]);
        }
    printf("\n");
    for(i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
            printf("%3d ",chess[i][j]);
        printf("\n");
    }
}

//回溯算法
void BackTrace(int t, int x, int y)
{
    if (t >= N * N) 
    //if(t>=37)
    {
        p++;
        OutPutChess();//输出结果
        exit(1);   //求得一个解时,退出程序
        //return;  //求得所有解
    }
    else
    {
        for (int i = 0; i < 8; ++i)
        {
            if (canJump(x + Jump[i][0], y + Jump[i][1]))
            {   //求下一个结点
                x += Jump[i][0];
                y += Jump[i][1];

                printf("(%2d,%2d)",x,y);//打印当结点
                chess[x][y] = t + 1;
                step[t] = i;
                BackTrace(t + 1, x, y);//递归调用
                //回溯
                chess[x][y] = 0;
                x -= Jump[i][0];
                y -= Jump[i][1];
            }
        }
        
    }
}
/**//**/
int main()
{
    int x = 0;
    int y = 0;
    chess[x][y] = 1;
    BackTrace(1, x, y);
    printf("All Results Number = %d ", p);
}

该算法最坏的时间复杂度为O（8^N*N）。这是一个相当大的数字，不能接受，但实际情况好得多。并且在37步的时候，开
始发生回溯,可通过改BackTrace中的第一个if中的参数发现。据说,总的回溯次数达300多百万次.
我的机子运行20分钟也没运行出结果.我们可以考虑,当N=8时,为2¹⁹²,即使对于2¹⁰⁰=1.3*10³⁰,对于一台每秒1万亿(10¹²)次操作的计算机,也需要4*10¹⁰才能完成,超过了45亿年---地球的估计年龄.
但是,该算法可以适当改进,考虑到:
即向前看两步，当每准备跳一步时，设准备跳到(x, y)点，计算(x, y)这一点可能往几个方向跳（即向前看两步），将这个数目设为(x, y)点的权值，将所  有可能的(x, y)按权值排序，从最小的开始，循环遍历所有可能的(x, y)，回溯求出结果。算法可以求出所有可能的马跳棋盘路径，算出一个可行 的结果很快，但在要算出所有可能结果时，仍然很慢，因为最坏时间复杂度本质上并没有改变，仍为O(8^(N * N)),但实际情况很好,在瞬间即可得到一个解,当然,要求得所有解,也需要很长的时间.
下面是实现这一思想的代码：

#include <stdio.h>
#include <stdlib.h>
/**//**/
//棋盘行数
const int N = 8;

int step[N * N] = {-1}; //保存每一步做出的选择
int chess[N][N] = {0}; //棋盘

int Jump[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {