本文实例为大家分享了C/C++实现马踏棋盘的具体代码，供大家参考，具体内容如下
问题描述：将马随机放在国际象棋的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步；
具体实现如下：
|
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
#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，不在棋盘则返回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 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;} //初始化棋盘上所有位置的值为-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"); } fclose(pfile);} int main(){ //进行棋盘上跳跃Trace初始化 initBoard(); if (HorseRoaming(g_StartPos) == 0) { //打印结果 printSteps(); } else { //未找到解 printf("Not found Result \n"); } return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/zzjj2008vi163/article/details/46551461
