由于今天的马踏棋盘算法并不是使用OC编写，所以，今天的标题也就不是"使用OC....."了，下面直接开始我们的正题，还是老规矩，先上一张图：
马踏棋盘示意图.png
我们的需求是，将"马"放在任意制定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。并且将马走的步数标记出来，也就是第一步就标记为1，第二步就标记为2、依次类推，直到马走完了64个位置之后那么就算完成了，下面我们直接来看代码，因为我在代码里就已经将思路标记上了，每一句代码几乎都有详细的注释：
#define MaxRow 8//最大行
#define MaxCol 8//最大列
int chess[MaxRow][MaxCol];//棋盘二维数组
#pragma mark - 马踏棋盘算法（骑士周游问题）
#pragma mark -
/**
对八种情况分析寻找下一步可以走的位置
@param x 当前马所在棋盘位置的x坐标
@param y 当前马所在棋盘位置的y坐标
@param count 不考虑边缘的情况，马在任意一位置的下一个位置都可能有八种情况，count就是对这八种情况进行判断
只要找到其中一种就返回1
@return 找到返回1，否则返回0
*/
int nextStep(int *x ,int *y,int count) {
switch(count)
{
case 1:
if(*x + 2 <= MaxCol - 1 && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)
{
*x += 2;
*y -= 1;
return 1;
}
break;
case 2:
if(*x + 2 <= MaxCol - 1 && *y + 1 <= MaxRow - 1 && chess[*x + 2][*y + 1] == 0)
{
*x += 2;
*y += 1;
return 1;
}
break;
case 3:
if(*x + 1 <= MaxCol - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)
{
*x += 1;
*y -= 2;
return 1;
}
break;
case 4:
if(*x + 1 <= MaxCol - 1 && *y + 2 <= MaxRow - 1 && chess[*x + 1][*y + 2] == 0)
{
*x += 1;
*y += 2;
return 1;
}
break;
case 5:
if(*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)
{
*x -= 2;
*y -= 1;
return 1;
}
break;
case 6:
if(*x - 2 >= 0 && *y + 1 <= MaxRow - 1 && chess[*x - 2][*y + 1] == 0)
{
*x -= 2;
*y += 1;
return 1;
}
break;
case 7:
if(*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)
{
*x -= 1;
*y -= 2;
return 1;
}
break;
case 8:
if(*x - 1 >= 0 && *y + 2 <= MaxRow - 1 && chess[*x - 1][*y + 2] == 0)
{
*x -= 1;
*y += 2;
return 1;
}
break;
default:
break;
}
return 0;
}
/**
深度优先搜索
@param x 开始搜索的x
@param y 开始搜索的y
@param step 第多少步
@return 返回1表示下一步可行 0表示不可行
*/
int TraversalChessBoard(int x ,int y ,int step) {
//临时变量记录当前位置x和y
int x1 = x,y1 = y;
//flag作为标记是否找到下一个位置 count为遍历的8中情况
int flag =0,count = 1;
//标记当前的位置已经被🐴踏过 标记为step，也就是刚刚走的是第多少步
chess[x][y] = step;
//当步数刚好等于棋盘的格子个数 就证明已经走完了
if (step == MaxRow * MaxCol) {
//成功 打印结果
Print();
return 1;
}
//没有走完就 寻找下一个位置并且将八种情况都走一遍
flag = nextStep(&x1, &y1, count);
//只要flag为0证明上一次没有找到下一步，这里我们把剩下的其他位置都走一遍
while (flag == 0 && count < MaxRow) {
//让走法+1
count++;
//让flag重新标记
flag = nextStep(&x1, &y1, count);
}
//当找到下一个位置了之后，就从找到的位置开始继续递归寻找
while (flag) {
// 递归调用走向下一个位置，因为在NextStep函数中直接修改了当前位置的坐标，所以此时的x1和y1就表示下一个可走位置的坐标
if (TraversalChessBoard(x1, y1, step+1)) {
return 1;
}
//如果不是返回1，那证明刚刚的路径没法走完 我们就回溯到上一个位置去
x1 = x;
y1 = y;
// 前count种可走位置的情况都判断过了，从count+1种情况继续判断
count++;
//没有走完就 寻找下一个位置并且将八种情况都走一遍
flag = nextStep(&x1, &y1, count);
//只要flag为0证明上一次没有找到下一步，这里我们把剩下的其他位置都走一遍
while (flag == 0 && count < MaxRow) {
//让走法+1
count++;
//让flag重新标记
flag = nextStep(&x1, &y1, count);
}
}
//如果八种情况都是没法找到合适的位置 那就从当前位置回退到上一个位置 返回0就行 而且将二维数组中的位置置为0 证明它没有走过
if (0 == flag) {
chess[x][y] = 0;
}
return 0;
}
/**
* 打印棋盘，棋盘中每个格子的数值就是遍历的次序
*/
void Print()
{
int i, j;
for(i = 0; i < MaxRow; i++)
{
for(j = 0; j < MaxCol; j++)
{
printf("%2d\t", chess[i][j]);
}
printf("\n");
}
printf("\n");
}
这里我需要对第一个方法也就是nextStep这个方法进行一下说明，这个方法是用于寻找马下一步要走的位置，假如我们当前要走到1这个位置，那么x需要-1 ，y则需要-2，然后再判断一下是否跑出了棋盘的位置，接着还需要判断1这个位置是否马已经走过了，如果上面我说的几种情况都满足了，那么就说明这个位置是可以走的，就返回1，这就是这个方法大概的意思，不考虑边缘情况下，马总共有8种方式可以走，因此这里通过一个switch对8中情况进行了考虑，接着就是TraversalChessBoard这个方法了，这个方法里面我已经写上了详细的注释了，应该都能看懂了，当然，注重要的是得理解，如果不理解，也是很难看明白的
