一个经典的趣味算法问题
马踏棋盘
【题目要求】
国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。编写一个C程序，实现马踏棋盘操作，要求用1～64这64个数字标注马移动的路径，也就是按照求出的行走路线，将数字1，2，……64依次填入棋盘的方格中，并输出。

解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索的思想。
我模仿该思路写了一个不用递归的算法，但不知道正确与否，现拿来分享一下，想请大家帮我检查一下，该算法是否有问题，或是提供一些验证实例或方法。当然，也希望您能提出一些改进的意见建议，谢谢！
我写的源代码如下：

C/C++ code

#include<stdio.h>#include<stdlib.h>int QiPan[8][8];struct LinkNode{    int i,j,M;    LinkNode *P,*N;};LinkNode *head;int len;void Clear();/*清空或初始化棋盘*/void Print();/*输出棋盘*/void InsertNode(int ii,int jj,int PM);/*插入节点*/void DeleteNode();/*删除节点*/bool MarkRun();/*马判断怎么走的过程。*/void main(){    Clear();    int x,y;    printf("请输马初始位置的x，y坐标：");    scanf("%d%d",&x,&y);    head=(LinkNode *)malloc(sizeof(LinkNode));    head->P=NULL;    head->N=NULL;    head->i=x;    head->j=y;    head->M=0;    len=1;    QiPan[x][y]=len;    bool f=MarkRun();    if(f)    {        printf("从该位置出发，走完棋盘的路线顺序如下：\n");        Print();    }    else        printf("从该位置出发，不能走完棋盘。\n");}/******************void Clear() 清空或初始化棋盘******************/void Clear()   /*清空或初始化棋盘*/{    for(int i=0;i<8;i++)        for(int j=0;j<8;j++)            QiPan[i][j]=0;}/**************void Print()输出棋盘*******************************/void Print()  //输出棋盘{    for(int i=0;i<8;i++)    {        for(int j=0;j<8;j++)            printf("%d   ",QiPan[i][j]);        printf("\n");    }    printf("\n");}/***************void InsertNode() 插入节点 ***********************/void InsertNode(int ii,int jj,int PM)/*插入节点*/{    head->M=PM;    LinkNode *a=(LinkNode *)malloc(sizeof(LinkNode));    a->i=ii;    a->j=jj;    a->M=0;    a->N=head;    head->P=a;    a->P=NULL;    head=a;    len++;    QiPan[ii][jj]=len;}/******************void DeleteNode()  删除节点*********************/void DeleteNode()/*删除节点*/{    LinkNode *D=head;    head=head->N;    head->P=NULL;    D->N=NULL;    QiPan[D->i][D->j]=0;    head->M+=1;    free(D);    len--;}/************bool MarkRun() 马判断怎么走的过程。*******************/bool MarkRun() /*马判断怎么走的过程。*/{    bool flag=false;    int x,y;    x=head->i;y=head->j;    while(len<=64)    {        if(head->M==0)            {                    if(QiPan[x-2][y+1]==0)                    InsertNode(x-2,y+1,1);                else if(QiPan[x-1][y+2]==0)                    InsertNode(x-1,y+2,2);                else if(QiPan[x+1][y+2]==0)                    InsertNode(x+1,y+2,3);                else if(QiPan[x+2][y+1]==0)                    InsertNode(x+2,y+1,4);                else if(QiPan[x+2][y-1]==0)                    InsertNode(x+2,y-1,5);                else if(QiPan[x+1][y-2]==0)                    InsertNode(x+1,y-2,6);                else if(QiPan[x-1][y-2]==0)                    InsertNode(x-1,y-2,7);                else if(QiPan[x-2][y-1]==0)                    InsertNode(x-2,y-1,8);            }        else                switch(head->M)            {                case 1:                    InsertNode(x-2,y+1,1);break;                case 2:                      InsertNode(x-1,y+2,2);break;                case 3:                    InsertNode(x+1,y+2,3);break;                case 4:                    InsertNode(x+2,y+1,4);break;                case 5:                    InsertNode(x+2,y-1,5);break;                case 6:                    InsertNode(x+1,y-2,6);break;                case 7:                    InsertNode(x-1,y-2,7);break;                case 8:                    InsertNode(x-2,y-1,8);break;                default:                    DeleteNode();            }        }                if(len==64)        flag=true;    return flag;}/***************************************************************/ 
 

[解决办法]
很好啊 不错 再接再厉
[解决办法]
nb,mark a litter
[解决办法]
死循环？
[解决办法]
曾经使用栈做贪心深搜,无回溯的得到结果.
[解决办法]
提示楼主,深搜是跑不出这个程序的,即便用了栈数据结构也会死住.

必须使用贪心策略,即优先跳到邻接可跳点最少的邻接点这个规则.


[解决办法]
或者使用队列做广搜,每个状态结点都要记录当前棋盘的样子,可以用二进制压缩存储,不解释.