算法详解---骑士走棋盘

（同样献给寒假还在肝题的老哥们。。。）

感觉这两道题在解释一件事，八皇后可以用dfs（深搜），也可以用广搜，而骑士走棋盘问题给我的感受就是在解释广搜算法的步骤。。。
建议看完本篇所讲题目再去看看八皇后，可能会有所受益。

骑士走棋盘问题中，骑士的走法为国际象棋的走法，类似中国象棋的马，骑士可以由任意一个位置出发，求如何不重复的走完所有位置。

问题解法：

骑士的走法，基本上可以用递归的方法来解决，但是纯粹的递归在维度大时相当没有效率。简单的说，先将最难的位置走完，接下来的路就是宽广，骑士所要走的下一步：为下一步再做选择时，所能走的步数最少的一步。使用这个方法，在不使用递归的情况下，可以有较高的几率找出走法，而这，就是广搜的精髓！

大致图解：

代码如下：

#include <iostream>
#include <iomanip>   //对标准输入/输出流操作的函数库
#define SIZE 8
using namespace std;
bool travel(int board[][SIZE],int x,int y);        
int possible(int board[][SIZE],int *nexti,int *nextj,int x,int y);
int min(int board[][SIZE],int *nexti,int *nextj,int count);  
void printBoard(int borad[][SIZE]);
int main()
{
    int start_x;
    int start_y;
    cout<<"输入初始位置"<<endl;
    cin>>start_x>>start_y;
    int board[SIZE][SIZE]={0};
    if(travel(board,start_x,start_y))cout<<"遍历成功!"<<endl;
    else cout<<"遍历失败!"<<endl;
    printBoard(board);
}
bool travel(int board[][SIZE],int x,int y)
{
    board[x][y]=1;                   //当前位置为第1次走的位置
    int nexti[SIZE]={0};
    int nextj[SIZE]={0};             //下一跳初始化
    int i=x;
    int j=y;
    int MAX=SIZE*SIZE;
    int count=0;
    for(int m=2;m<=MAX;m++)          //遍历棋盘
    {
        count=possible(board,nexti,nextj,i,j);//得到可能的下一跳数目
        if(count==0)return false;    //无可走方向,遍历失败
        int min_Direction=min(board,nexti,nextj,count);//在多个可能方向中查找下一跳方向最少的方向
        i=nexti[min_Direction];      //下一跳位置坐标
        j=nextj[min_Direction];
        board[i][j]=m;               //当前位置为第m次走的位置
    }
    return true;
}
int possible(int board[][SIZE],int *nexti,int *nextj,int x,int y)
{
    int mvi[SIZE]={-2,-1,1,2,2,1,-1,-2};    //下一跳可能的八个方向(x坐标y坐标)
    int mvj[SIZE]={1,2,2,1,-1,-2,-2,-1};
    int count=0;
    for(int i=0;i<SIZE;++i)
    {
        int tmpx=x+mvi[i];
        int tmpy=y+mvj[i];
        if(tmpx<0||tmpy<0||tmpx>SIZE-1||tmpy>SIZE-1)continue; //越界,不是可行方向
        if(board[tmpx][tmpy]==0)                  //未走过,找到一个可能方向
        {
            nexti[count]=tmpx;
            nextj[count]=tmpy;
            count++;
        }
    }
    return count;                              //返回可能的方向数
}
int min(int board[][SIZE],int *nexti,int *nextj,int count)
{
    int mvx[SIZE]={-2,-1,1,2,2,1,-1,-2};
    int mvy[SIZE]={1,2,2,1,-1,-2,-2,-1};
    int exist[SIZE]={0};                   //记录该方向的下一跳方向的数目
    int min_direction=-1;                  //初始化最小方向数的方向
    if(count==1)min_direction=0;           //只有一个可行方向
    else
    {
        for(int i=0;i<count;++i)           //在所有可行方向中遍历
        {
            for(int j=0;j<SIZE;++j)        //计算每一个方向下一跳的数目
            {
                int tmpx=nexti[i]+mvx[j];
                int tmpy=nextj[i]+mvy[j];
                if(tmpx<0||tmpy<0||tmpx>SIZE-1||tmpy>SIZE-1)continue;
                if(board[tmpx][tmpy]==0)
                {
                    exist[i]++;
                }
            }
        }
        int min=exist[0];                 //取其中最小数目的方向
        min_direction=0;
        for(int i=1;i<count;++i)          //此处count开始错为SIZE,一直未查出错误
                                          //exist数组只有count位不为0
        {
            if(exist[i]<min)
            {
                min=exist[i];
                min_direction=i;
            }
        }
    }
    return min_direction;
}
void printBoard(int board[][SIZE])
{
     for(int i=0;i<SIZE;++i)
     {
         for(int j=0;j<SIZE;++j)
         {
             cout<<setw(2)<<board[i][j]<<"  ";
         }
         cout<<endl;
     }
}

而在这位博主的博客中给出的代码，貌似更为简洁易懂一些，如下：

#include <iostream>
#include <cstdio>

using namespace std;

int pos[8][8] = {0};

int travel(int, int);

int main()
{
    int i, j, startX, startY;
    printf("Please input a starting point: ");
    scanf("%d%d", &startX, &startY);
    if(travel(startX, startY)) {
        printf("Travel finished\n");
    }else {
        printf("Travel failed\n");
    }
    for(i=0; i<8; i++) {
        for(j=0; j<8; j++) {
            printf("%2d ", pos[i][j]);
        }
        printf("\n");
    }
    return 0;
}

int travel(int x, int y) {
    int i, j, k, l, m;
    int tmpX, tmpY;
    int count, min, tmp;

    //骑士可走的八个方向(顺时针)
    int ktmoveX[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    int ktmoveY[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

    //下一步坐标
    int nextX[8] = {0};
    int nextY[8] = {0};

    //记录每个方向的出路的个数
    int exists[8] = {0};

    //起始用1标记位置
    i = x;
    j = y;
    pos[i][j] = 1;

    //遍历棋盘
    for(m=2; m<=64; m++) {
        //初始化八个方向出口个数
        for(l=0; l<8; l++) {
            exists[l] = 0;
        }
        l = 0; //计算可走方向

        //试探八个方向
        for(k=0; k<8; k++) {
            tmpX = i + ktmoveX[k];
            tmpY = j + ktmoveY[k];
            //边界 跳过
            if(tmpX<0 || tmpY<0 || tmpX>7 || tmpY>7) {
                continue;
            }
            //可走 记录
            if(pos[tmpX][tmpY] == 0) {
                nextX[l] = tmpX;
                nextY[l] = tmpY;
                l++;    //可走方向加1
            }
        }
        count = l;
        //无路可走 返回
        if(count == 0) {
            return 0;
        //一个方向可走 标记
        }else if(count == 1) {
            min = 0;
        //找出下个位置出路个数
        }else {
            for(l=0; l<count; l++) {
                for(k=0; k<8; k++) {
                    tmpX = nextX[l] + ktmoveX[k];
                    tmpY = nextY[l] + ktmoveY[k];
                    if(tmpX<0 || tmpY<0 || tmpX>7 || tmpY>7) {
                        continue;
                    }
                    if(pos[tmpX][tmpY] == 0) {
                        exists[l]++;
                    }
                }
            }
            //找出下个位置出路最少的方向
            min = 0;
            tmp = exists[0];
            for(l=0; l<count; l++) {
                if(exists[l] < tmp) {
                    tmp = exists[l];
                    min = l;
                }
            }
        }
        //用序号标记走过的位置
        i = nextX[min];
        j = nextY[min];
        pos[i][j] = m;
    }
    return 1;
}

深为受教！