本文共 1785 字,大约阅读时间需要 5 分钟。
//马踏棋盘主要要考虑三个因素:
//第一:马走的位置用Move数组表示,以及棋盘的大小不再是8*8,而是12*12;
//第二:只要找到马可以踏的下一个位置,就进行递归,只有一只进行递归,这是一种理想状态;
/第三:也是最不好想的一点,如果在当前位置,准备进行下一个位置,但是没有找到,就需要回溯,回溯需要将计数器--,并且将这个位置赋值为0,表示这个位置没走过,因为回溯本身就在for循环中,所以,循环会自己判断进行下一个位置判定;
//马踏棋盘;#include//棋盘,其中i=0,1,11,12和j=0,1,11,12表示围墙,马可以踏但是不算在计数中;int M[12][12]={0}; int cnt=0; //标记马已走的方格数; int sum=0; //标记马走完全程的具体方案数; int move[8][2]= //初始马当前位置向其周围相邻八个日字的 x,y的偏移量,也就是马可以走的位置一共为八个;{ { 2, 1}, { 1, 2}, {-1, 2}, {-2, 1}, {-2,-1}, {-1,-2}, { 1,-2}, { 2,-1}}; //输出马踏棋盘的解 void PrintChess(){ for(int i=2;i<10;i++) { for(int j=2;j<10;j++) printf("%3d",M[i][j]); printf("\n"); } printf("\n\n\n");}//判断马可以走的位置;void Horse(int x,int y) //马永远踏的是 x,y位置,而不是 a,b;{ if(cnt==64) //临界值,马走日字全部踏完,成功求出问题解; { sum++; //解的个数; printf("第%d组解:\n",sum); PrintChess(); //输出; return ; } for(int i=0;i<8;i++) { int a=x+move[i][0]; //拿到当前马位置相邻的 8 个日字的 x 坐标; int b=y+move[i][1]; //拿到当前马位置相邻的 8 个日字的 y 坐标; if(M[a][b]==0) //判断当前马位置相邻的日字是否已被访问; { M[a][b]=++cnt; //标志已被访问; Horse(a,b); //从当前马的位置继续往下访问; cnt--; //回溯到这里,将计数的值--; M[a][b]=0; //并且将这个位置清空,进行下一次循环或者跳出循环; } } } int main(void){ printf("***马踏棋盘左右解***\n\n"); //在8*8的外层再加上两层,确保8*8方格中的每一个格子都有8种不同的日字选择; for(int i=0;i<12;i++) { for(int j=0;j<12;j++) { if(i==0||i==1||i==10||i==11||j==0||j==1||j==10||j==11){ M[i][j]=-1; } } } //从起始位置开始求得所有解; //坐标(2,2)马可以踏,将求得的位置解++; M[2][2]=++cnt; //递归调用当前当前位置附近的 8 个日字,看看是否满足条件; //马从坐标(2,2)开始; Horse(2,2); return 0; }
//结果截图;