跳马问题
跳马问题算法代码
跳马问题也称骑士遍历问题：在6*6方格的棋盘上，从任意指定的方格出发，为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。(跳马问题采用回溯法求解最多只能求到6*6，当棋盘再大时采用回溯法无法求出答案。复杂度太大，计算机承受不了。。。当M*N的棋盘时，若M*N 是奇数，则一定无解)
【算法描述】
本题有较多方法求解，在此仅对回溯法进行分析。
一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是：(2,1)、(2,-1)、(1,2)、(1,-2)、(-2,1)、(-2,-1)、(-1,2)、(-1,-2)。从中任选择一个方向前进，到达新的位置。在从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置已经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前进，就再回退到上一位置……
#include
#include
#include
const int n=6; // 表示棋盘的长和高n
int qiban[n+1][n+1]; // 记录棋盘是否被跳过
static int cmq; // 步数
int con=1,OK=0; // 没有被使用
int xLabel,yLabel;
void shuchu()
{
cout<<'\t';
for(int i1=1;i1<=n;i1++)
cout< for(int i=1;i<=n;i++) { cout< cout< for(int j=1;j<=n;j++) { cout< } cout< } } int tiaoma(int x,int y) { if(cmq ==n*n && ((x-2==xLabel && y+1 == yLabel) ||(x-1==xLabel && y+2 == yLabel) ||(x+1==xLabel && y+2== yLabel) || (x+2 == xLabel && y+1 == yLabel) ||(x+2 == xLabel && y-1 == yLabel) ||(x+1== xLabel && y-2==yLabel) ||(x-2==xLabel && y-1==yLabel) ||(x-1==xLabel && y-2==yLabel))) { shuchu(); OK=1; return 0; } if(1 <= x-2 && y+1 <= n && qiban[x-2][y+1] == 0) { qiban[x-2][y+1]=++cmq; // 1 tiaoma(x-2,y+1); if(1<=x-1&&y+2<=n&&qiban[x-1][y+2]==0) { qiban[x-1][y+2]=++cmq; // 2 tiaoma(x-1,y+2); } if(x+1<=n&&y+2<=n&&qiban[x+1][y+2]==0) { qiban[x+1][y+2]=++cmq; // 3 tiaoma(x+1,y+2); } if(x+2<=n&&y+1<=n&&qiban[x+2][y+1]==0) { qiban[x+2][y+1]=++cmq; // 4 tiaoma(x+2,y+1); } if(x+2<=n&&1<=y-1&&qiban[x+2][y-1]==0) { qiban[x+2][y-1]=++cmq; // 5 tiaoma(x+2,y-1); } if(x+1<=n&&1<=y-2&&qiban[x+1][y-2]==0) qiban[x+1][y-2]=++cmq; // 6 tiaoma(x+1,y-2); } if(1<=x-1&&1<=y-2&&qiban[x-1][y-2]==0) { qiban[x-1][y-2]=++cmq; // 7 tiaoma(x-1,y-2); } if(1<=x-2&&1<=y-1&&qiban[x-2][y-1]==0) { qiban[x-2][y-1]=++cmq; // 8 tiaoma(x-2,y-1); } cmq --; qiban[x][y] = 0; // 回朔 return 0; } int main() { unsigned beg,end; beg=(unsigned)time(NULL); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) qiban[i][j]=0; for(i=1;i<=n;i++) //该处分别计算从点(1,1)到点(n,n)作为起始点，可以找到哪些回路for(int j=1;j<=n;j++) { xLabel= i; yLabel = j; cmq = 1; for(int k1=1;k1<=n;k1++) for(int k2=1;k2<=n;k2++) qiban[k1][k2]=0; qiban[i][j] = 1; tiaoma(i,j); } if(OK!=1) { cout< } end=(unsigned)time(NULL); cout< return 0; } 回溯法其实也是一种穷举的方法，因此在进行递归调用时，一定要先判断下一步动作是否满足条件，这样可以减少递归次数。 上面的程序会枚举出所有的满足条件的解。如果只想找到一个解就结束，怎么办呢？有一种办法是：修改回调函数，让它返回一个布尔变量，使其当找到一个解时返回true，如果还没有找到解返回false。【问题拓展】 根据上述算法，可以得到回溯算法解类似问题的一般算法： ＃i nclude //全局变量 void search(int x) { //如果找到匹配的，则输出结果 //改变标志位，环境变量等等：这些改变就相当于完成一步动作，在跳马问题中就是马向前跳一步，在后面的八皇后问题中就相当于放置了一个皇后 //search(x+1)，即进行下一步动作；可能有多个分支，如跳马问题中马可以往八个方向跳，在后面的八皇后问题中每个皇后可能有8个摆放位置 //回退：还原标志位，环境变量等 } void main() { search(初始值); }