在一个8x8的表格中，起始点任意，且马只可以走日字，要求使用非递归程序给出一种能够走遍棋盘上所有点的一种走法。

    由于是数据结构的作业，并且在栈那一章，且要求使用非递归，明显要求是使用深搜，自己起初便写了个深搜(最简单的那种，结果时间复杂度过高，要好几分钟才可以跑出结果)，后来便是用了贪心优化，然后秒出结果。

   首先对于最简单的暴力来说，十分的不可行。因为对于棋盘上每个点，都可以拓展出8个点(如果不考虑出界问题的话)，这样就形成了一个八叉树，深度为64。如果考虑最坏的情况，那么大约需要次操作，而且实际操作次数必然会大于这个数。对于计算机每秒千万级别的运算来说，还是小巫见大巫，所以十分不推荐这么写。接下来说下贪心优化。

   优化的主要点在于，在接下来8个点中，如何选择下一个点。在正常的程序中是按照一定顺序进行选择的。而贪心优化则是选择8各点中每个点可拓展点最少的点。因为这样的话会有更大的几率发现终点(具体原因我也不太明白)，还有人对下一个点的选择是随机的，好像也可以极大的优化程序。下面就是鄙人的代码：

#include<bits/stdc++.h>
using namespace std;
int book[8][8],sx,sy,head,tail;
int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};
struct node{
    int x,y;
    int next[8];
    int vis[8];
}sta[1000000];
bool check(int x,int y){
    if(x<0||y<0||x>7||y>7||book[x][y])
        return false;
    return true;
}
void qiu(int x){
    int xx,yy,sum;
    for(int q=0;q<8;q++){
        sum=0;
        xx=sta[x].x+dx[q];
        yy=sta[x].y+dy[q];
        if(check(xx,yy)){
            for(int w=0;w<8;w++){
                if(check(xx+dx[w],yy+dy[w])) sum++;
            }
            sta[x].next[q]=sum;
        }
        else sta[x].next[q]=-1;
    }
    return ;
}
void print(){
    int count=0;
    for(int q=head;q<tail;q++){
        count++;
        cout<<sta[q].x*8+sta[q].y+1<<" ";
        if(count%8==0&&count) cout<<endl;
    }
    return ;
}
void dfs(){
    head=0;tail=1;
    sta[head].x=sx;
    sta[head].y=sy;
    qiu(head);
    while(head<tail){
        int min=999999,u=-1;
        for(int q=0;q<8;q++){
            if(sta[tail-1].next[q]<min&&sta[tail-1].next[q]!=-1) { min=sta[tail-1].next[q]; u=q; }
        }
        if(u==-1) { book[sta[tail-1].x][sta[tail-1].y]=0; tail--; }
        else{
            sta[tail].x=sta[tail-1].x+dx[u];
            sta[tail].y=sta[tail-1].y+dy[u];
            book[sta[tail].x][sta[tail].y]=1;            
            sta[tail-1].next[u]=-1;
            qiu(tail);
            tail++;
        }
        if(tail==64) { print(); break; }
    }
    return ;
}
int main(){
    memset(book,0,sizeof(book));
    srand((int)time(NULL));
    sx=rand()%8;
    sy=rand()%8;
    book[sx][sy]=1;
    dfs();
    return 0;
}