我整理的文章：跳马问题深化。最后提出了一个问题，请大家解决。
【问题描述】
跳马问题也称骑士遍历、马踏棋盘问题：在8*8方格的棋盘上，从任意指定的方格出发，为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【回溯算法】
程序可以这样来写：
#include <stdio.h>
//全局变量
void search(int x)
{
//改变标志位，环境变量等等：这些改变就相当于完成一步动作，在跳马问题中就是马向前跳一步，在后面的八皇后问题中就相当于放置了一个皇后
//如果找到匹配的，则输出结果
//否则，找到当前步可能的路径，然后search(x+1)，即进行下一步动作；这里可能有多个分支，如跳马问题中马可以往八个方向跳，在后面的八皇后问题中每个皇后可能有8个摆放位置，每个分支都要列举出来，以便回溯时使用
//回退：还原标志位，环境变量等等，即清除当前步的痕迹
}
void main()
{
search(初始值);
}
下面是跳马问题的完整程序：
//马踏棋盘的递归程序
//棋盘大小：8*8
//起始位置：0,0
#define M 8
#define N 8
#include <stdio.h>
int map[M][N];
int count=0;//记录马共跳的步数
int countnum=0;//用于统计走法种数
int direction[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};//马可能前进的8个方向
void print_map();//打印出马跳的路径
void go(int i,int j);//马向(i,j)点跳
void main()
{
freopen( "out.txt ", "w ",stdout);
for(int k=0;k <M;k++)
for(int l=0;l <N;l++)
map[k][l]=0;
go(0,0);
printf( "End at:%ld\n ",countnum);
}
void go(int i,int j)
{
//改变标志位，环境变量等等：这些改变就相当于完成一步动作，在跳马问题中就是马向前跳一步
count++;//计数器
map[i][j]=count;//棋盘置当前步数
//如果找到匹配的，则输出结果
if(count==64)//如果已经遍历棋盘则打印一次走法
{
print_map();
}
//否则，找到当前步可能的路径，然后search(x+1)，即进行下一步动作；这里可能有多个分支，如跳马问题中马可以往八个方向跳，每个分支都要列举出来，以便回溯时使用
else
{
int m,n;
for (int k=0;k <8;k++)
{
m=i+direction[k][0];
n=j+direction[k][1];
if(m> =0 && m <M && n> =0 && n <N)
if(map[m][n]==0)
{
go(m,n);
}
}
}
//回退：还原标志位，环境变量等
map[i][j]=0;//回退，置零
count--;//计数器减
}
void print_map()
{
for(int i=0;i <M;i++)
{
for(int j=0;j <N;j++)
printf( "%3d ",map[i][j]);
printf( "\n ");
};
countnum=countnum+1;
printf( "Now Count:%d\n\n ",countnum);
}
【相关问题】
我原来有两个疑惑：
(1).回溯算法跟深度优先搜索算法的区别在哪里？上面用回溯法来解跳马问题，其实就是一种深度优先搜索的思想。
(2).8*8的跳马问题复杂度比较大，如果策略选择不好，很可能半天出不来结果。如上述程序从(1,1)起跳很快能找到解；但是如果从(3,3)起跳，很长时间也出不来结果。上述程序中，8个方向的先后顺序组合一个策略，如果把8个方向的先后顺序换一下，如先顺序是：(2,1)、(2,-1)、(1,2)、(1,-2)、(-2,1)、(-2,-1)、(-1,2)、(-1,-2)，也从(1,1)起跳，但是很难得到结果。不知道8个方向策略的选择有什么窍门，我至今没有找出来。
经过研究，终于明白了一些。
对于第一个问题，实际上，几乎所有算法书上，都有专门一章专门介绍回溯算法，但是深度优先搜索，一般是当作一种解决特定问题时说的。也就是说，深度优先搜索是运用回溯算法的体现。
对于第二个问题，策略的选择是有规律的，这就是带有启发式的回溯算法，运用它可以对算法进行优化，加快搜索速度。
【启发式搜索】
对于跳马问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。也就是说在当前位置优先选一个走起来比较“艰难”的方向来推进。加入这种启发式规则之后，运行效果加快了很多，无论从哪个位置起跳，很快就能找到解。
那么，怎么在上述程序的基础上加入启发式思想呢？首先，引入一个难易矩阵，如下。它表示从每一个点出发，可以朝几个方向跳，换言之，也就是可以有多少方向能到达此点。方向越多，说明越容易跳到。
int accessibility[M][N]=// 棋盘相应点的难易值
{{ 2,3,4,4,4,4,3,2 },
{ 3,4,6,6,6,6,4,3 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 3,4,6,6,6,6,4,3 } ,
{ 2,3,4,4,4,4,3,2 } };
要让马先跳难跳的位置，就必须对每一个点的所有方向进行排序，排序后，就是当前点马的跳法策略。在此，可以用冒泡排序进行排序，把马不可能跳的方向也方向(即马会超出边界的方向)也排到后面，这样，马如果在(i,j)点，只要依次跳accessibility[i][j]个方向即可，而后面的方向是不可能跳到的。
加入启发式思想后，对上述程序改进如下。如果想找一条循环路径，即马跳到最后一步之后，再跳一步又回到了起点，只要把go函数里的print_map()上两行加入即可。运用此程序，很快就能找到解。
/*
对于骑士游历问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，
当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。
也就是说在当前位置优先选一个走起来比较 "艰难 "的方向来推进。
*/
//马踏棋盘的递归程序
//棋盘大小：8*8
//起始位置：0,0
#define M 8
#define N 8
#include <stdio.h>
int map[M][N];
int count=0;
int countnum=0; //用于统计走法种数
int accessibility[M][N]=// 棋盘相应点的难易值
{{ 2,3,4,4,4,4,3,2 },
{ 3,4,6,6,6,6,4,3 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 4,6,8,8,8,8,6,4 } ,
{ 3,4,6,6,6,6,4,3 } ,
{ 2,3,4,4,4,4,3,2 } };
int direction[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};//马可能前进的8个方向
int newDirection[8][2];//排序后的方向
void print_map();
bool go(int i,int j);
void sort(int a,int b);
void main()
{
freopen( "out.txt ", "w ",stdout);
for(int k=0;k <M;k++)
for(int l=0;l <N;l++)
map[k][l]=0;
go(0,0);
printf( "End at:%ld\n ",countnum);
}
bool go(int i,int j)
{
count++;//计数器
map[i][j]=count;//棋盘置当前步数
if(count==64)//如果已经遍历棋盘则打印一次走法
{
//for (int a=0;a <8;a++)
//if ((i + direction[a][0])==0 && (j + direction[a][1])==0)
print_map();
}
else
{
int m,n;
sort(i,j);
for (int k=0;k <accessibility[i][j];k++)//实际上不是每个点都有8个方向，应该是accessibility[i][j]个方向
{
m=i+newDirection[k][0];
n=j+newDirection[k][1];
if(m> =0 && m <M && n> =0 && n <N)
if(map[m][n]==0)
{
go(m,n);
sort(i,j);
}
}
//sort(i,j);
}
map[i][j]=0;//回退，置零
count--;//计数器减
return false;//注意：如果函数没有返回值，会默认返回true
}
void sort(int a,int b)//对(a,b)点的8个方向进行重新排序，把较难走的排在前面
{
int i,j,swap_x,swap_y;
for (i=0;i <8;i++)
{
newDirection[i][0] = direction[i][0];
newDirection[i][1] = direction[i][1];
}
//冒泡排序：把马越容易跳着的点的方向放到后面；另外，也把不可能的方向放到后面
for (i=8-1;i> =0;i--)
for (j=0;j <i;j++)
{
if(!(a+newDirection[j+1][0] < 0 || a+newDirection[j+1][0] > = M || b+newDirection[j+1][1] < 0 || b+newDirection[j+1][1] > = N))
{
if(a+newDirection[j][0] < 0 || a+newDirection[j][0] > = M || b+newDirection[j][1] < 0 || b+newDirection[j][1] > = N)
{
swap_x = newDirection[j][0];
swap_y = newDirection[j][1];
newDirection[j][0] = newDirection[j+1][0];
newDirection[j][1] = newDirection[j+1][1];
newDirection[j+1][0] = swap_x;
newDirection[j+1][1] = swap_y;
}
else if(accessibility[a+newDirection[j][0]][b+newDirection[j][1]] > accessibility[a+newDirection[j+1][0]][b+newDirection[j+1][1]])
{
swap_x = newDirection[j][0];
swap_y = newDirection[j][1];
newDirection[j][0] = newDirection[j+1][0];
newDirection[j][1] = newDirection[j+1][1];
newDirection[j+1][0] = swap_x;
newDirection[j+1][1] = swap_y;
}
}
}
}
void print_map()
{
for(int i=0;i <M;i++)
{
for(int j=0;j <N;j++)
printf( "%3d ",map[i][j]);
printf( "\n ");
};
countnum=countnum+1;
printf( "Now Count:%d\n\n ",countnum);
}
【问题】
go函数里调用了两次sort函数，第一次是在给选择策略作准备，第二次是恢复原来的策略，为回溯作准备。
这里有一个问题：第二次sort必须紧接着go(m,n)，而不能写在for循环结束之后，否则会打印出很多相同的路径。
这个问题我调试了很久，也没有找出原因。
完整的文章：http://longmang.blog.edu.cn/user2/longmang/archives/2007/1648764.shtml
文章下载：http://longmang.blog.edu.cn/UploadFiles/2007-2/224155834.rar
请大家帮忙解决问题呀。
[解决办法]
不是你自己说每次go()调用都回改变newdire数组嘛 当然要go()返回要马上改 要不然再次循环时根据上次调用的ij排序了
[解决办法]
不要光写代码 写点想法大家才好讨论
