跳马问题骑士遍历问题 ppt课件.ppt

跳马问题跳马问题也称骑士遍历问题:在n*n方格的棋盘上,从任意指定的方格出发,为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。跳马问题骑士遍历问题问题分析如下图所示,一只马在棋盘的某一点,它可以朝8个方向前进,方向向量分别是:(-2,1)、(-1,2)(1,2)、(2,1)、(2,-1)、(1,-2)、(-1,-2)、(-2,-1)。跳马问题骑士遍历问题从中任选择一个方向前进,到达新的位置。在从新的位置选择一个方向前进,继续,直到无法前进为止。无法前进可能有如下原因:下一位置超出边界、下一位置已经被访问过。当马已经无法前进时,就回退到上一位置,从新选择一个新的方向前进;如果还是无法前进,就再回退到上一位置,以此类推。跳马问题骑士遍历问题经分析,本问题可以运用回溯法的思想求解:,一个可行的解就是从根节点到叶子节点的一条路径。。跳马问题骑士遍历问题代码#include<>#include<>#include<>constintn=6;//表示棋盘的长和高nintqipan[n+1][n+1];//记录棋盘是否被跳过staticintcmq;//步数intOK=0;//没有被使用intxLabel,yLabel;voidshuchu(){cout<<'\t';for(inti1=1;i1<=n;i1++)cout<<i1<<"列"<<'\t';for(inti=1;i<=n;i++){cout<<endl;cout<<i<<"行"<<'\t';for(intj=1;j<=n;j++){cout<<qipan[i][j]<<'\t';}cout<<endl;}}跳马问题骑士遍历问题inttiaoma(intx,inty){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;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-1][y+2]=++cmq;//2tiaoma(x-1,y+2);}if(x+1<=n&&y+2<