本文共 6685 字，大约阅读时间需要 22 分钟。

题目描述

将棋子“马”随机的放在国际象棋棋盘Board[8][8]的某个方格中，“马”按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上所有的64个方格。

题目要求

编写非递归程序，求出“马”的行走路线，并按求出的行走路线将数字1-64依次填入一个8x8的方阵并输出。

分析 x 1

一看题目说是8x8棋盘，要求走遍棋盘，首先想到的便是直接深搜即可，但是后面说到要求非递归程序，这也简单，自己把递归的那一部分改为用栈来实现即可（马走棋盘肯定会遇到走不下去的情况，所以需要储存之前已经走过的点，而“悔棋”肯定是从当前这一步往之前返回，所以是一个后进先出的结构——栈）。

定义

typedef struct _horse{
       int x;  //横坐标    int y;  //纵坐标    int s;  //下一步的方向}HORSE;int chessboard[8][8];   //棋盘int Next[8][2] = {
   {
   2,1}, {
   1,2}, {
   -1,2}, {
   -2,1}, {
   -2,-1}, {
   -1,-2}, {
   1,-2}, {
   2,-1}};  //方向int cnt = 1;            //计数器stack
   
     horse;
   

执行函数

bool judge(int a, int b){
       if(a < 0 || a > 7 || b < 0 || b > 7)    //边界        return false;    return true;}void Horse(int x, int y){
       HORSE temp;    int a,b;	//记录当前马位置附近的坐标    int i = 0;    chessboard[x][y] = cnt;	//标记当前起始位置已被访问     temp.x = x;	//记录当前马的位置    temp.y = y;    while(cnt < 64)    {
           for(; i < 8; i++)        {
               a = temp.x + Next[i][0];            b = temp.y + Next[i][1];            if(judge(a,b) && chessboard[a][b] == 0)     //判断            {
                   break;            }        }        if(i < 8)	//能够访问当前马位置附近的日点        {
               chessboard[a][b] = ++cnt;            temp.s = i;            horse.push(temp);            memset(&temp, 0, sizeof(HORSE));            temp.x = a;            temp.y = b;            i = 0;        }        else	//回溯        {
               --cnt;            chessboard[temp.x][temp.y] = 0;            HORSE tt = horse.top();            horse.pop();            temp.x = tt.x;            temp.y = tt.y;            i = tt.s;            ++i;	//继续搜索从当前马位置访问的点的下一个点继续访问        }    }}

完成后测试了一下，只有（0，0）可以跑出来，可见这种暴力的方式效率实在是太低…

分析 x 2

上面的暴力试探方式效率实在太低了，所以我们要优化一下代码。把书继续往后翻，有提到将马的初始步入栈，计算其8个方向的权值，将其按升序排列，马从最小权值的点开始走，无路可走时回溯（权值就是一个点下一步能走的点的总数）。这是一种贪心的思想，那么既然是贪心，我们可不可以再贪心一些，每一步直接走权值最小的点，不再回溯，看能不能走完。

执行函数

void Horse(int x, int y){
       HORSE temp;    int a,b;    //记录当前马位置附近的坐标    chessboard[x][y] = cnt; //标记当前起始位置已被访问     temp.x = x; //记录当前马的位置    temp.y = y;    while(cnt < 64)    {
           int h_min = 8;      //权值最小的点        int tx,ty,ti;       //记录权值最小的点的信息        for(int i = 0; i < 8; i++)        {
               a = temp.x + Next[i][0];            b = temp.y + Next[i][1];            if(judge(a,b) && chessboard[a][b] == 0)     //判断            {
                   int step = steps(a,b);   //计算权值                if(step < h_min)         //更新权值最小的点                {
                       h_min = step;                        tx = a;                    ty = b;                    ti = i;                }                        }        }        //直接走权值最小的点        chessboard[tx][ty] = ++cnt;        temp.s = ti;        //temp.step = h_min;        horse.push(temp);        memset(&temp, 0, sizeof(HORSE));        temp.x = tx;        temp.y = ty;    }}

这次测试了一下，效率大大的提高了，但是我们是“最”贪心的方法，所以我们要测试一下，看能不能从任意点出发都能走完棋盘。

分析 x 3

好吧，既然只有一个点不能按照我们最贪心的方式走完，那么我们就只对这一个点特殊处理一下。处理方式即就是分析2时所说的按权值大小排序，从最小的开始走。

最终版本

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;/* 马踏棋盘 */typedef struct _horse{
       int x;  //横坐标    int y;  //纵坐标    int s;  //下一步的方向    int step;   //下一步的权值    int flag;  //特殊点用}HORSE;int chessboard[8][8];   //棋盘int Next[8][2] = {
   {
   2,1}, {
   1,2}, {
   -1,2}, {
   -2,1}, {
   -2,-1}, {
   -1,-2}, {
   1,-2}, {
   2,-1}};  //方向int cnt = 1;            //计数器stack
       
         horse;//判别bool judge(int a, int b){
       if(a < 0 || a > 7 || b < 0 || b > 7)    //边界        return false;    return true;}//从小到大排序bool cmp(HORSE& a, HORSE& b){
       return a.step < b.step;}//计算权值int steps(int a, int b){
       int sum = 0;    for(int i = 0; i < 8; i++)    {
           int x = a + Next[i][0];        int y = b + Next[i][1];        if(judge(x,y) && chessboard[x][y] == 0)            ++sum;    }    return sum;}//执行过程void Horse(int x, int y){
       HORSE temp;    int a,b;    //记录当前马位置附近的坐标    chessboard[x][y] = cnt; //标记当前起始位置已被访问     temp.x = x; //记录当前马的位置    temp.y = y;    while(cnt < 64)    {
           int h_min = 8;      //权值最小的点        int tx,ty,ti;       //记录权值最小的点的信息        for(int i = 0; i < 8; i++)        {
               a = temp.x + Next[i][0];            b = temp.y + Next[i][1];            if(judge(a,b) && chessboard[a][b] == 0)     //判断            {
                   int step = steps(a,b);   //计算权值                if(step < h_min)         //更新权值最小的点                {
                       h_min = step;                        tx = a;                    ty = b;                    ti = i;                }                        }        }        //直接走权值最小的点        chessboard[tx][ty] = ++cnt;        temp.s = ti;        //temp.step = h_min;        horse.push(temp);        memset(&temp, 0, sizeof(HORSE));        temp.x = tx;        temp.y = ty;    }}//特殊点执行过程（2，4）void Horse_2(int x, int y){
       HORSE temp;    HORSE horse_2[8];    memset(horse_2, 0, sizeof(HORSE));    int a,b;    int flag = 0;   //记录该走那一个点了    chessboard[x][y] = cnt;    temp.x = x;    temp.y = y;    while(cnt < 64)    {
           int k = 0;        for(int i = 0; i < 8; i++)        {
               a = temp.x + Next[i][0];            b = temp.y + Next[i][1];            if(judge(a,b) && chessboard[a][b] == 0)     //找出可走的点            {
                   int step = steps(a,b);                horse_2[k].x = a;                horse_2[k].y = b;                horse_2[k].s = i;                horse_2[k].step = step;                ++k;            }        }        sort(horse_2, horse_2 + k, cmp);    //按权值从小到大排序        for(int i = 0; i < k; i++)            horse_2[i].flag = i;            if(k > 0 && flag < k)   //有路可走        {
               chessboard[horse_2[flag].x][horse_2[flag].y] = ++cnt;            temp.s = horse_2[flag].s;            temp.step = horse_2[flag].step;            temp.flag = horse_2[flag].flag;            horse.push(temp);            memset(&temp, 0, sizeof(HORSE));            temp.x = horse_2[flag].x;            temp.y = horse_2[flag].y;            flag = 0;        }        else    //回溯        {
               --cnt;            chessboard[temp.x][temp.y] = 0;            HORSE tt = horse.top();            horse.pop();            temp.x = tt.x;            temp.y = tt.y;            flag = tt.flag;            ++flag; //走下一个点        }    }}//输出void print(){
       for(int i = 0; i < 8; i++)    {
           for(int j = 0; j < 8; j++)            cout << chessboard[i][j] << ' ';        cout << endl;    }}int main(){
       int x,y;    cout << "从那个点开始: ";    cin >> x >> y;    if(x == 2 && y == 4)        Horse_2(x,y);    else        Horse(x,y);    print();    return 0;}
       
      
     
    
   

转载地址：http://ojqwi.baihongyu.com/