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

《跳马问题、骑士遍历问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、跳马问题跳马问题也称骑士遍历问题：在n*n方格的棋盘上，从任意指定的方格出发，为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。问题分析如下图所示，一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是：(-2,1)、(-1,2)(1,2)、(2,1)、(2,-1)、(1,-2)、(-1,-2)、(-2,-1)。从中任选择一个方向前进，到达新的位置。在从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置已经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前

2、进，就再回退到上一位置，以此类推。经分析，本问题可以运用回溯法的思想求解：1.该问题的解空间的组织形式是一颗八叉树，一个可行的解就是从根节点到叶子节点的一条路径。2.控制策略则是马必须在棋盘内。代码#include#include#includeconstintn=6;//表示棋盘的长和高nintqipan[n+1][n+1];//记录棋盘是否被跳过staticintcmq;//步数intOK=0;//没有被使用intxLabel,yLabel;voidshuchu(){cout<<'t';fo

3、r(inti1=1;i1<=n;i1++)cout<

4、

5、(x-1==xLabel&&y+2==yLabel)

6、

7、(x+1==xLabel&&y+2==yLabel)

8、

9、(x+2==xLabe

10、l&&y+1==yLabel)

11、

12、(x+2==xLabel&&y-1==yLabel)

13、

14、(x+1==xLabel&&y-2==yLabel)

15、

16、(x-2==xLabel&&y-1==yLabel)

17、

18、(x-1==xLabel&&y-2==yLabel))){shuchu();OK=1;return0;}if(1<=x-2&&y+1<=n&&qipan[x-2][y+1]==0){qipan[x-2][y+1]=++cmq;//1tiaoma(x-2,y+1);}if(1<=x-1&&y+2<=n&&qipan[x-1][y+2]==0){qipan[x-

19、1][y+2]=++cmq;//2tiaoma(x-1,y+2);}if(x+1<=n&&y+2<=n&&qipan[x+1][y+2]==0){qipan[x+1][y+2]=++cmq;//3tiaoma(x+1,y+2);}if(x+2<=n&&y+1<=n&&qipan[x+2][y+1]==0){qipan[x+2][y+1]=++cmq;//4tiaoma(x+2,y+1);}if(x+2<=n&&1<=y-1&&qipan[x+2][y-1]==0){qipan[x+2][y-1]=++cmq;//5tiaoma(x+2,y-1);}if(x

20、+1<=n&&1<=y-2&&qipan[x+1][y-2]==0){qipan[x+1][y-2]=++cmq;//6tiaoma(x+1,y-2);}if(1<=x-1&&1<=y-2&&qipan[x-1][y-2]==0){qipan[x-1][y-2]=++cmq;//7tiaoma(x-1,y-2);}if(1<=x-2&&1<=y-1&&qipan[x-2][y-1]==0){qipan[x-2][y-1]=++cmq;//8tiaoma(x-2,y-1);}cmq--;qipan[x][y]=0;//回朔return0;}intmain()

21、{for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)qipan[i][j]=0;for(i=1;i<=n;i++)//该处分别计算从点(1,1)到点(n,n)作为起始点，可以找到哪些回路for(intj=1;j<=n;j++){xLabel=i;yLabel=j;cmq=1;for(intk1=1;k1<=n;k1++)for(intk2=1;k2<=n;k2++)qipan[k1][k2]=0;qipan[i][j]=1;tiaoma(i,j);}if(OK!=1){cout<

22、