1、原题中文大意
对于一个8*8的棋盘，用下列的方式编号
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
如果它走63步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，设计一个算法，从给定的起点出发，找出它的一条周游路线。马的走法是“日”字形路线。
输入有若干行。每行一个整数N(1<=N<=64)，表示马的起点。最后一行用-1表示结束，不用处理。
对输入的每一个起点，求一条周游线路。对应地输出一行，有64个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
2、算法思想及解题用到的主要数据结构
这是一道比较明显要用深度优先搜索算法的题目，求出马的周游路线。用广度优先除了浪费时间、空间，给解题增加困难以外是没有任何好处的。
解题时用一个结构体来存储路线中的节点，结构体中包含在棋盘中的横坐标、纵坐标、子节点的数目这3个属性。
因为我们的目的是找出一条完整的路径，也就是从初始的父节点开始用正确的方式搜索到第63层子树，所以显而易见，先搜索子节点数目较少的节点会大大地提高效率，这样有主要2个好处：（1）如果路径正确，只需要很小的时间和空间复杂度就可以达到目标；（2）如果路径不正确，也容易返回然后走到正确的道路上。
这是本题用到的主要思想，主要的数据结构就是结构体。
3、详细解题思路
对于一个输入的编号值，首先要转化为对应的节点，然后从这个节点开始进行深度优先搜索。将这个节点标记为true，即已走过。
计算出当前节点的可以走向的下一个节点的数目，并得到所有的子节点，然后对所有的子节点进行排序，含子节点较少的子节点优先级比较高，然后从优先级比较高的子节点进行下一步的搜索，直到搜索到第63层节点。
我们需要一个二维数组flag[8][8]来存储节点是否走过的信息，开始时都为false，走过则标记为true；一个二维数组nextStep[8][2]来表示可能的8个子节点与当前节点的坐标差；一个一维数组road[64]来记录路线。
深度有先算法中有一个参数degr来传递搜索树的深度，每向下搜索一层，则degr加1，能加到63说明沿着这条路有解，路线存储在数组road[]中。
4、逐步求精算法描述（含过程及变量说明）
// 三个全局变量：
bool flag[8][8]; // 记录每个节点是否已经走过，走过设为true，未走过为false
//左上开始顺时针旋转的方向,记录马下一步可能走的八个方向
int nextStep[8][2]={1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};
int road[64]={0}; // 记录马走过的编号序列
// 计算子节点的数目：
/*
计算某个节点有多少个子节点，子节点为从当前位置可以走向的下一位置
依次对八个方向进行判断，得出子节点的数目
*/
inline int num(int a, int b){
int n=0;
for(int i=0;i<8;i++){
int x=a+nextStep[i][0];
int y=b+nextStep[i][1];
if(judge(x,y))
n++;
}
return n;
}
// 存储节点的数据结构：
/*
节点的数据结构为结构体，
节点有3个属性：节点的横坐标，纵坐标，子节点的数目
*/
struct node{
int x;
int y;
int nextNum;
node(){
x=-1;
y=-1;
nextNum=-1;
}
node(int a, int b){
x=a;
y=b;
nextNum=num(a,b);
}
};
// 深度优先算法：
/*
深度优先搜索函数，
用一个堆栈保存搜索的节点，在搜索的过程中子节点数目少的节点优先搜索，用sort()函数排序确定。
*/
bool dfs(node start,int degr){
if(degr==63){
road[degr]=nodeToNum(start);
return true;
}
int a=start.x;
int b=start.y;
flag[a][b]=true;
vector<node> sear;
road[degr]=nodeToNum(start);
for(int i=0;i<8;i++){
node ne=getNode(start, i);
if(judge(ne.x, ne.y))
sear.push_back(ne);
}
sort(sear.begin(), sear.end(),cmp);
for(int j=0; j<sear.size();j++){
if(dfs(sear[j],degr+1))
return true;
}
flag[a][b]=false;
return false;
}
5、注释清单
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
bool flag[8][8]; //记录每个节点是否已经走过，走过设为true，未走过为false
//左上开始顺时针旋转的方向,记录马下一步可能走的八个方向
int nextStep[8][2]={1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};
int road[64]={0}; //记录马走过的编号序列
/*
判断某个节点是否可走，
判断条件为此节点在棋盘上，并且还未走过
*/
bool judge(int a,int b){
if(a>=0 && a<=7 && b>=0 && b<=7 && !flag[a][b])
return true;
return false;
}
/*
计算某个节点有多少个子节点，子节点为从当前位置可以走向的下一位置
依次对八个方向进行判断，得出子节点的数目
*/
inline int num(int a, int b){
int n=0;
for(int i=0;i<8;i++){
int x=a+nextStep[i][0];
int y=b+nextStep[i][1];
if(judge(x,y))
n++;
}
return n;
}
/*
节点的数据结构为结构体，
节点有3个属性：节点的横坐标，纵坐标，子节点的数目
*/
struct node{
int x;
int y;
int nextNum;
node(){
x=-1;
y=-1;
nextNum=-1;
}
node(int a, int b){
x=a;
y=b;
nextNum=num(a,b);
}
};
/*
根据当前位置和要走的方向得到子节点
*/
node getNode(node no, int dir){
int a=no.x+nextStep[dir][0];
int b=no.y+nextStep[dir][1];
return node(a,b);
}
/*
比较两个节点的优先级，子节点数目少的节点的优先级要高，
用于深度优先搜索的排序
*/
bool cmp(node n1, node n2){
return n1.nextNum < n2.nextNum;
}
/*
根据节点的编号，转化为相应的节点
*/
node numToNode(int k){
int x=(k-1)/8;
int y=(k-1)%8;
if(judge(x,y))
return (node(x,y));
}
/*
将节点转化为相应的编号
*/
int nodeToNum(node no){
return (8*no.x+no.y+1);
}
/*
深度优先搜索函数，
用一个堆栈保存搜索的节点，在搜索的过程中子节点数目少的节点优先搜索，用sort()函数排序确定。
*/
bool dfs(node start,int degr){
if(degr==63){
road[degr]=nodeToNum(start);
return true;
}
int a=start.x;
int b=start.y;
flag[a][b]=true;
vector<node> sear;
road[degr]=nodeToNum(start);
for(int i=0;i<8;i++){
node ne=getNode(start, i);
if(judge(ne.x, ne.y))
sear.push_back(ne);
}
sort(sear.begin(), sear.end(),cmp);
for(int j=0; j<sear.size();j++){
if(dfs(sear[j],degr+1))
return true;
}
flag[a][b]=false;
return false;
}
int main(){
/*
调试用代码
for(int j=0;j<8;j++)
cout<<nextStep[j][0]<<" "<<nextStep[j][1]<<endl;
*/
int n;
while(cin>>n && n!=-1 && n>=1 && n<=64){
memset(flag,0,sizeof(flag));
node start=numToNode(n);
dfs(start,0);
cout<<road[0];
for(int i=1;i<64;i++)
cout<<" "<<road[i];
cout<<endl;
}
return 0;
}
6、测试数据（5-10组有梯度的测试数据,要考虑边界条件）
1
1 18 33 50 60 54 64 47 62 56 39 24 7 13 3 9 26 41 58 52 35 25 10 4 19 2 17 11 5
20 14 8 23 29 12 6 16 22 32 15 30 40 55 45 28 34 49 43 37 31 48 63 46 61 51 57 4
2 59 53 36 21 27 44 38
5
5 15 32 47 64 54 60 50 33 18 1 11 17 2 12 6 16 22 7 24 39 56 62 45 55 61 51 57 4
2 59 49 34 44 27 10 25 35 41 58 52 37 43 28 38 53 63 48 31 21 4 14 8 23 29 46 40
30 36 19 13 3 9 26 20
10
10 25 42 57 51 61 55 40 23 8 14 4 19 2 17 34 49 59 53 63 48 31 16 6 12 27 33 50
60 54 64 47 62 56 46 52 58 41 35 29 44 38 32 15 21 36 30 45 39 24 7 13 3 9 26 43
37 20 5 22 28 11 1 18
22
22 16 6 12 2 17 34 49 59 53 63 48 31 14 8 23 40 55 61 46 56 62 47 64 54 60 50 44
38 32 15 5 11 1 18 33 43 58 52 37 27 21 4 10 25 42 57 51 41 35 29 39 45 28 13 7
24 30 36 19 9 26 20 3
35
35 41 58 52 62 56 39 24 7 13 3 9 26 20 5 15 32 47 64 54 60 50 33 18 1 11 17 2 12
22 16 6 23 8 14 29 19 25 10 4 21 27 37 31 48 63 46 40 30 36 42 57 51 61 55 45 2
8 34 49 43 53 59 44 38
48
48 63 53 59 49 34 17 2 12 6 16 31 14 8 23 40 55 61 46 56 62 47 64 54 60 50 44 38
32 15 5 11 1 18 33 43 58 52 37 22 28 45 39 24 7 13 30 20 3 9 26 41 51 57 42 36
21 27 10 4 19 25 35 29
52
52 58 41 51 57 42 59 49 34 17 2 12 6 16 31 48 63 53 47 64 54 60 50 33 43 37 27 4
4 61 55 40 46 56 62 45 39 24 7 22 32 38 23 8 14 29 35 25 10 4 19 9 26 36 21 15 3
0 13 28 11 5 20 3 18 1
64
64 47 62 56 39 24 7 13 3 9 26 41 58 52 42 57 51 61 55 40 46 63 48 54 60 45 30 36
53 59 49 43 33 50 44 34 17 2 19 25 35 29 23 8 14 4 10 20 37 31 16 6 12 27 21 38
32 15 5 22 28 11 1 18
-1
7、对时间复杂度，空间复杂度方面的分析、估算及程序优化的分析和改进
在sicily上的runtime是0sec，速度还是比较快的。
如果在进行深度优先搜索的时候，不优先搜索子节点较少的节点，会大大增加时间和空间的复杂度，甚至无法通过sicily的测试，所以，一定要选择子节点较少的节点优先进行搜索。