《跳马问题骑士遍历问题》由会员分享，可在线阅读，更多相关《跳马问题骑士遍历问题（8页珍藏版）》请在金锄头文库上搜索。
1、跳马问题 跳马问题也称骑士遍历问题：在n*n方格的棋盘上，从任意指定的方格出发，为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 问题分析如下图所示，一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是： (-2,1)、 (-1,2) (1,2)、 (2,1)、(2,-1) 、(1,-2)、 (-1,-2)、(-2,-1)。 从中任选择一个方向前进，到达新的位置。在从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置已经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前进，就再回退到上一位
2、置，以此类推。经分析，本问题可以运用回溯法的思想求解：1.该问题的解空间的组织形式是一颗八叉树，一个可行的解就是从根节点到叶子节点的一条路径。2.控制策略则是马必须在棋盘内。代码v#includev#include v#include vconst int n=6; / 表示棋盘的长和高nvint qipann+1n+1; / 记录棋盘是否被跳过vstatic int cmq; / 步数vint OK=0; / 没有被使用vint xLabel,yLabel;vvoid shuchu()vv coutt;v for(int i1=1;i1=n;i1+)v couti1列t;v for(int
3、i=1;i=n;i+)v v coutendl;v couti行t;v for(int j=1;j=n;j+)v v coutqipanijt;v v coutendl;v v vint tiaoma(int x,int y)vvif(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=yLa
4、bel) |(x-2=xLabel & y-1=yLabel) |(x-1=xLabel & y-2=yLabel)vv shuchu();v OK=1;v return 0;vv v if(1 = x-2 & y+1 = n & qipanx-2y+1 = 0)v v qipanx-2y+1=+cmq; / 1v tiaoma(x-2,y+1);v v if(1=x-1&y+2=n&qipanx-1y+2=0)v v qipanx-1y+2=+cmq; / 2v tiaoma(x-1,y+2);v v if(x+1=n&y+2=n&qipanx+1y+2=0)v v qipanx+1y+2=
5、+cmq; / 3v tiaoma(x+1,y+2);v v if(x+2=n&y+1=n&qipanx+2y+1=0)v v qipanx+2y+1=+cmq; / 4v tiaoma(x+2,y+1);v v vif(x+2=n&1=y-1&qipanx+2y-1=0)v v qipanx+2y-1=+cmq; / 5v v tiaoma(x+2,y-1);v v if(x+1=n&1=y-2&qipanx+1y-2=0)v v qipanx+1y-2=+cmq; / 6v tiaoma(x+1,y-2);v v if(1=x-1&1=y-2&qipanx-1y-2=0)v v qipan
6、x-1y-2=+cmq; / 7v tiaoma(x-1,y-2);v v if(1=x-2&1=y-1&qipanx-2y-1=0)v v qipanx-2y-1=+cmq; / 8v tiaoma(x-2,y-1);v v v cmq -;v qipanxy = 0; / 回朔vreturn 0;vvint main()vv for(int i=1;i=n;i+)v for(int j=1;j=n;j+)v qipanij=0;v v for(i=1;i=n;i+) /该处分别计算从点(1,1)到点(n,n)作为起始点，可以找到哪些回路v for(int j=1;j=n;j+)v v xLabel= i;v yLabel = j;v cmq = 1;v for(int k1=1;k1=n;k1+)v for(int k2=1;k2=n;k2+)v qipank1k2=0;v qipanij = 1;v tiaoma(i,j);v v v if(OK!=1)v v coutendl当nn时无回路endl;v v return 0;v
