C++马踏棋盘算法
zzjj2008vi163 人气:0问题描述:将马随机放在国际象棋的8×8棋盘Board[0~7][0~7]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。
问题求解算法简述:
1.深度优先遍历+回溯法
2.贪心算法+深度优先遍历+回溯法
解法1描述:
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步;
解法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]; //用来表示Horse跳到下一位置为第几跳,起跳位置为第0跳 int g_HorseSteps = 0; //定义Horse的起跳位置,可以输入;若输入非法则使用默认起跳位置(0,0) SPOS g_StartPos={0,0}; //检查位置有效性, 若位置在棋盘内则返回1,不在棋盘则返回0 int 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); } //检查位置是否已经跳过,若跳过则位置上记录经过该位置时为第几跳,若未被跳过则值为棋盘初始值-1 int checkUsed(SPOS tPos) { return g_ArrChessBoard[tPos.nPosX][tPos.nPosY] != -1; } //根据偏移量获取位置有效性 void getNextStepListByOffSet(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep, int offSetX, int offSetY) { //定义Horse的可跳方向 //分别为右上(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 + offSetX*DirectionList[i].nPosX; tPos.nPosY = curPos.nPosY + offSetY*DirectionList[i].nPosY; //若跳点在棋盘内,且跳点未被跳过则可以作为下一跳点 if (checkPos(tPos) && !checkUsed(tPos)) { NextStepList[(*NumOfValidStep)++] = tPos; } } } //获取下一跳位置列表, 下一跳位置列表最多存在8个,所以固定传入数组8 //只返回有效的位置列表, NumOfValidStep中存储有效位置列表个数 void getNextStepList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep) { //X坐标移动2格,Y坐标移动1格检查 getNextStepListByOffSet(curPos, NextStepList, NumOfValidStep, 2, 1); //X坐标移动1格,Y坐标移动2格检查 getNextStepListByOffSet(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 HorseRoaming(SPOS curPos) { SPOS NextStepList[8]; //记录curPos的下一跳点列表,最多存在8个可能跳点,使用数组表示 int NumOfValidStep = 0;//记录下一跳列表中的跳点个数 int i = 0; int nRet = 1; //添加跳点的Trace记录,并刷新跳点的计数 g_ArrChessBoard[curPos.nPosX][curPos.nPosY] = g_HorseSteps++; //若已经经过棋盘上所有节点则表示找到马踏棋盘路径,退出 if (g_HorseSteps == CHESS_BOARD_LINE_NUM*CHESS_BOARD_COLUM_NUM) { return 0; } //使用普通DFS进行路径查找 //getNextStepList(curPos, NextStepList, &NumOfValidStep); //使用贪心算法获取有效列表 getNextGreedList(curPos, NextStepList, &NumOfValidStep); for (; i < NumOfValidStep; i++) { //进行递归求解 nRet = HorseRoaming(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_HorseSteps--; return 1; } //初始化棋盘上所有位置的值为-1 void 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"); } fclose(pfile); } int main() { //进行棋盘上跳跃Trace初始化 initBoard(); if (HorseRoaming(g_StartPos) == 0) { //打印结果 printSteps(); } else { //未找到解 printf("Not found Result \n"); } return 0; }
加载全部内容