C/C++实现马踏棋盘算法

本文实例为大家分享了c/c++实现马踏棋盘的具体代码，供大家参考，具体内容如下

问题描述：将马随机放在国际象棋的8×8棋盘board[0～7][0～7]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

问题求解算法简述：

1.深度优先遍历+回溯法

2.贪心算法+深度优先遍历+回溯法

解法1描述：

1.使用一个二维数组step[8][8]= {-1}来表示棋盘，起跳位置做为当前位置step[i][j]，设置numofsteps = 0；

2.设置当前位置st什么叫素数ep[i][j] =numofsteps++,

若numofsteps == 64表示已经获取解，退出；

若numo李晟个人资料fsteps < 64，获取位置step[i][j]的下一跳可达位置列表nextsteplist，设置n=0；【可达位置列表必须保证该位置有效，且未被经过】

3.从nextsteplist获取下一个未处理位置nextsteplist[n]，将nextsteplist[n]作为当前位置step[i][j],执行第2步

若列表已经结束，则设置当前step[i][j] = -1

若step[i][j]==起跳位置，表示无解，退出

否则设置numofsteps–，回溯到上一跳位置，在上一跳位置继续执行第3步；

解法2描述：

1.使用一个二维数组step[8][8]= {-1}来表示棋盘，起跳位置做为当前位置step[i][j]，设置numofsteps = 0；

2.设置当前位置step[i][j] =numofsteps++,

若numofsteps==64表示已经获取解，退出；

若numofsteps<64，获取位置step[i][j]的下一跳可达位置列表nextsteplist，设置n=0；【可达位置列表必须保证该位置有效，且未被经过】

3.从nextsteplist获取下一个未处理位置nextsteplist[n]，将nextsteplist[n]作为当前位置step[i][j],执行第2步

若列表已经结束，则设置当前step[i][j] = -1

若step[i][j]==起跳位置，表示无解，退出

否则设置numofsteps–，回溯到上一跳位置，在上一跳位置继续执行第3步；

具体实现如下：

#include<stdio.h>//定义棋盘的行数和列数#define chess_board_line_num 10#define chess_board_colum_num 10//定义棋盘上位置的结构体typedef struct{ int nposx; int nposy;}spos;//使用一个二维数组来表示棋盘int g_arrchessboard[chess_board_line_num][chess_board_colum_num];//用来表示hor跳到下一位置为第几跳，起跳位置为第0跳int g_horsteps = 0;//定义hor的起跳位置，可以输入；若输入非法则使用默认起跳位置(0,0)spos g_startpos={0,0};//检查位置有效性, 若位置在棋盘内则返回1，不在棋盘则返回0int checkpos(spos tpos){ //x/y坐标不在棋盘内则位置不在棋盘内  return !(0 > tpos.nposx || tpos.nposx +1 > chess_board_line_num || 0 > tpos.nposy || tpos.nposy + 1 > chess_board_colum_num);}//检查位置是否已经跳过，若跳过则位置上记录经过该位置时为第几跳，若未被跳过则值为棋盘初始值-1int checkud(spos tpos){ return g_arrchessboard[tpos.nposx][tpos.nposy] != -1;}//根据偏移量获取位置有效性void getnextsteplistbyofft(spos curpos, spos nextsteplist[8], int* numofvalidstep, int offtx, int offty){ //定义hor的可跳方向 //分别为右上（1,1）、右下（1，-1）、左上（-1，1）、左下（-1，-1） //原始坐标+方向位移得到新的跳点 static spos directionlist[4] = {{1,1},{1,-1},{-1,1},{-1,-1}};  spos tpos; //存储可能的跳点，该跳点不一定有效 int i = 0; for (; i < 4; i++) {  tpos.nposx = curpos.nposx + offtx*directionlist[i].nposx;  tpos.nposy = curpos.nposy + offty*directionlist[i].nposy;  //若跳点在棋盘内，且跳点未被跳过则可以作为下一跳点  if (checkpos(tpos) && !checkud(tpos))  {   nextsteplist[(*numofvalid西南政法大学分数线step)++] = tpos;  } }}//获取下一跳位置列表, 下一跳位置列表最多存在8个，所以固定传入数组8//只返回有效的位置列表， 这个杀手不太冷片尾曲numofvalidstep中存储有效位置列表个数void getnextsteplist(spos curpos, spos nextsteplist[8], int* numofvalidstep){ //x坐标移动2格，y坐标移动1格检查  getnextsteplistbyofft(curpos, nextsteplist, numofvalidstep, 2, 1);   //x坐标移动1格，y坐标移动2格检查 getnextsteplistbyofft(curpos, nextsteplist, numofvalidstep, 1, 2); }//冒泡排序void sortbynextstepnum(spos nextsteplist[8], int* numofvalidstep, int nsubvalidstep[8]){ int tmpn; spos tmppos; int i = 0; int j = 0; int maxstepnum = *numofvalidstep; for (; i < maxstepnum;补水美白产品排行榜 i++) {  for (j = 1; j < maxstepnum - i; j++)  {   if (nsubvalidstep[j] < nsubvalidstep[j-1])   {    //进行位置互换，进行冒泡    tmpn = nsubvalidstep[j];    nsubvalidstep[j] = nsubvalidstep[j-1];    nsubvalidstep[j-1] = tmpn;        //进行对应的pos互换    tmppos = nextsteplist[j];    nextsteplist[j] = nextsteplist[j-1];    nextsteplist[j-1] = tmppos;   }  } }}//使用贪心算法获取下一位置列表，即对返回的有效列表根据出口进行升序排列void getnextgreedlist(spos curpos, spos nextsteplist[8], int* numofvalidstep){  spos subnextsteplist[8]; //用于缓存下一跳点列表的中每个跳点的下一跳点列表 int nsubvalidstep[8] = {0,0,0,0,0,0,0,0}; //用于存储下一跳点列表中每个跳点的下一跳点个数  int i = 0; //先获取所有的可跳节点 getnextsteplist(curpos, nextsteplist, numofvalidstep);  //获取子跳点的下一跳点个数 for(; i< *numofvalidstep; i++) {  getnextsteplist(nextsteplist[i], subnextsteplist, &nsubvalidstep[i]); }  //使用冒泡排序 sortbynextstepnum(nextsteplist, numofvalidstep, nsubvalidstep);}//以输入pos为起点进行马踏棋盘//返回0 表示找到正确跳跃路径//返回-1 表示已经完成所有跳点的尝试，不存在可行方案//返回1 表示选中的下一跳并非可行路径，需要重新选择一个跳点进行尝试int horroaming(spos curpos){  spos nextsteplist[8];  //记录curpos的下一跳点列表，最多存在8个可能跳点，使用数组表示 int numofvalidstep = 0;//记录下一跳列表中的跳点个数 int i = 0; int nret = 1;  //添加跳点的trace记录，并刷新跳点的计数 g_arrchessboard[curpos.nposx][curpos.nposy] = g_horsteps++;  //若已经经过棋盘上所有节点则表示找到马踏棋盘路径，退出 if (g_horsteps == chess_board_line_num*chess_board_colum_num) {  return 0; }   //使用普通dfs进行路径查找 //getnextsteplist(curpos, nextsteplist, &numofvalidstep);  //使用贪心算法获取有效列表 getnextgreedlist(curpos, nextsteplist, &numofvalidstep);  for (; i < numofvalidstep; i++) {  //进行递归求解  nret = horroaming(nextsteplist[i]);    if (1 != nret)    {   //求解结束   return nret;    }   }   //若回到起点位置，且起点的所有可能跳点均已尝试过，则说明未找到遍历棋盘方案 if (curpos.nposx == g_startpos.nposy && curpos.nposy == g_startpos.nposy) {  return -1; }   //回溯：回退棋盘上的trace记录，并返回上层 g_arrchessboard[curpos.nposx][curpos.nposy] = -1; g_horsteps--; return 1;}//初始化棋盘上所有位置的值为-1void initboard(){ int i,j; //设置循环控制变量 for (i = 0; i< chess_board_line_num; i++) {   for (j = 0; j< chess_board_colum_num; j++)  {   g_arrchessboard[i][j] = -1;  } }}//将棋盘上记录的跳跃trace打印到文件中void printsteps(){ int i,j;  file* pfile = fopen("output.txt","wb+");  for (i = 0; i< chess_board_line_num; i++) {  for (j = 0; j< chess_board_colum_num; j++)  {   fprintf(pfile,"%2d ", g_arrchessboard[i][j]);  }  fprintf(pfile,"\r\n"); }  fclo(pfile);}int main(){ //进行棋盘上跳跃trace初始化 initboard(); if (horroaming(g_startpos) == 0) {  //打印结果  printsteps(); } el {  //未找到解  printf("not found result \n"); } return 0;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持www.887551.com。