跳马问题、骑士遍历问题.pptVIP

跳马问题 跳马问题也称骑士遍历问题：在n*n方格的棋盘上，从任意指定的方格出发，为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 问题分析 如下图所示，一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是： (-2,1)、 (-1,2) (1,2)、 (2,1)、(2,-1) 、(1,-2)、 (-1,-2)、(-2,-1)。 从中任选择一个方向前进，到达新的位置。在从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置已经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前进，就再回退到上一位置，以此类推。 经分析，本问题可以运用回溯法的思想求解： 1.该问题的解空间的组织形式是一颗八叉树，一个可行的解就是从根节点到叶子节点的一条路径。 2.控制策略则是马必须在棋盘内。 代码 #includeiostream.h #include time.h #include stdlib.h const int n=6; // 表示棋盘的长和高n int qipan[n+1][n+1]; // 记录棋盘是否被跳过 static int cmq; // 步数 int OK=0; // 没有被使用 int xLabel,yLabel; void shuchu() { cout\t; for(int i1=1;i1=n;i1++) couti1列\t; for(int i=1;i=n;i++) { coutendl; couti行\t; for(int j=1;j=n;j++) { coutqipan[i][j]\t; } coutendl; } } 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 qipan[x-2][y+1] == 0) { qipan[x-2][y+1]=++cmq; // 1 tiaoma(x-2,y+1); } if(1=x-1y+2=nqipan[x-1][y+2]==0) { qipan[x-1][y+2]=++cmq; // 2 tiaoma(x-1,y+2); } if(x+1=ny+2=nqipan[x+1][y+2]==0) { qipan[x+1][y+2]=++cmq; // 3 tiaoma(x+1,y+2); } if(x+2=ny+1=nqipan[x+2][y+1]==0) { qipan[x+2][y+1]=++cmq; // 4 tiaoma(x+2,y+1); } if(x+2=n1=y-1qipan[x+2][y-1]==0) { qipan[x+2][y-1]=++cmq; // 5 tiaoma(x+2,y-1); } if(x+1=n1=y-2qipan[x+1][y-2]==0) { qipan[x+1][y-2]=++cmq; // 6 tiaoma(x+1,y-2); } if(1=x-11=y-2qipan[x-1][y-2]==0) { qipan[x-1][y-2]=++cmq; // 7 tiaoma(x-1,y-2); } if(1=x-21=y-1qipan[x-2][y-1]==0) { qipan[x-2][y-1]=++cmq; // 8 tiaoma(x-2,y-1); } cmq --; qipan[x][y] = 0; // 回朔 return 0; } int main