问题描述：假设国际象棋棋盘有5*5共25个格子。设计一个程序，使棋子从初始位置（棋盘编号为1的位置）开始跳马，能够把棋盘的格子全部都走一遍，每个格子只允许走一次。要求：
1）：输出一个解（用二维数组来记录马跳的过程，即[步号，棋盘格编号]），左上角为第一步起点；
2）：求总共有多少解；
*注：国际象棋的棋子是在格子中间的。 题目如下图
问题分析：由于国际象棋的棋子是在格子中间而不是线的交点处（这一点与中国象棋不同），所以我们可以将国际象棋棋盘看做是一个5行5列的二维数组，数组的每个元素代表棋盘上的一个格子（中国象棋里数组的一个元素代表一个交点）。数组从左往右、从上往下依次编号为1至25，代码如下
int a[5][5]={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}}; //将棋盘看成一个5行5列的二维数组a[5][5]，从左上角开始编号为1，一直到右下角编号为25
同时题目要求我们每个格子只能经过一次，所以我们需要再定义一个5行5列的标记数组对应棋盘的格子，通过标记数组的值来判断对应的棋盘格是否已经走过。
int a0[5][5]={0}; //a0[][]是标记数组，对应棋盘的每一个格子，初始值为0，用来判断每个格子是否已经走过，如果已经走过，则对应的值为1
同时我们还需要定义一个整形变量来记录步号，一个整形变量来记录总的解数，一个整形数组来记录每一步的棋盘格编号
int step[26]={0},answer_num; //answer_num是总的解数 一维数组step[]记录的是马走每一步经过的棋盘编号，因为步数是从1开始，到25结束，所以数组的长度为26，这样最后一个数的下标为25int step_num=0,flag=1; //step_num表示第几步 flag是答案输出标记
这样以来所有的准备工作就做好了，全部代码如下
#include<stdio.h>int step[26]={0},answer_num; //answer_num是总的解数 一维数组step[]记录的是马走每一步经过的棋盘编号，因为步数是从1开始，到25结束，所以数组的长度为26，这样最后一个数的下标为25int step_num=0,flag=1; //step_num表示第几步 flag是答案输出标记int a[5][5]={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}}; //将棋盘看成一个5行5列的二维数组a[5][5]，从左上角开始编号为1，一直到右下角编号为25int a0[5][5]={0}; //a0[][]是标记数组，对应棋盘的每一个格子，初始值为0，用来判断每个格子是否已经走过，如果已经走过，则对应的值为1//check()是判断格子是否合法的函数，返回一个整数，参数是格子在二维数组a[5][5]中的下标int check(int x,int y){int result;if(x<0||x>=5||y<0||y>=5||a0[x][y]==1) //不合法的情况有两种，要么格子在二维数组中的下标越界，要么这一格已经走过result=0; //不合法则返回0elseresult=1; //合法则返回1return result;}//search()是求解从编号为1的格子开始把棋盘全部格子走一遍的步骤的函数，有两个参数，分别是格子在二位数组a[5][5]中的横、纵坐标，取值范围均为0--4void search(int x,int y){int i;if(check(x,y)==1) //当格子合法时，才继续下列操作，否则什么也不做{ step[++step_num]=a[x][y]; //将这一格的编号记录在step[]数组中，同时步数step_num+1if(step_num==25) //只要步数到达25步，说明已经求得了一种解{answer_num++; //总解数answer_num+1if(flag==1)//当flag==1时，输出一种解{printf("one answer:\n");for(i=1;i<=25;i++)printf(" [%d,%d]\n",i,step[i]);}flag=0; //当已经输出一种解后令flag的值为0，不再输出后面的解}a0[x][y]=1; //同时将对应位置的a0[][]数组的值置为1，表示这一格已经走过//遍历其他8个方向，寻找其他可能的解search(x-2,y-1);search(x-1,y+2);search(x-1,y-2);search(x+2,y+1);search(x+2,y-1);search(x+1,y-2);search(x-2,y+1);search(x+1,y+2);//由于要求出所有的解法，所以当step_num等于25时退出递归，同时把对应位置的a0[][]数组的值置为0，并且退回到24步，去寻找其他第25步的可能。如果没有其他第25步的可能，则退回到第23步，寻找其他第24步的可能，以此类推下去，直到找到所有可能的解法step_num--;a0[x][y]=0;}}int main(){search(0,0); //棋子从棋盘格编号为1的位置开始跳马，而棋盘格编号为1的格子在二维数组中的下标为0 0printf("the total answer number is:%d\n",answer_num);return 0;}
如果觉得《国际象棋马走日（华科软院上机）》对你有帮助，请点赞、收藏，并留下你的观点哦！
