马踏棋盘算法

由于今天的马踏棋盘算法并不是使用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这个方法了，这个方法里面我已经写上了详细的注释了，应该都能看懂了，当然，注重要的是得理解，如果不理解，也是很难看明白的，今天就介绍这么多吧，今天的文章主要用于记录，防止以后忘记了没地方看，所以写的不好，大家不要喷，有什么没看明白的可以留言或私信。非常乐意解答。