象棋中马的遍历

算法 棋盘 递归

问题描述

在N*N棋盘上，任意一个位置放置一个棋子马，要能选择一套合适的移动路线，按象棋中“马走日”的移动规则不重复地遍历棋盘上每一个位置点。

基本要求

起始位置坐标由用户输入任意指定，然后依次输出所遍历的每个位置坐标。

基本思路:

使用二维数组代表棋盘,用bool标记是否走过该道路

使用递归的思想,每次尝试8个方向

如果可以,继续下一次尝试,否则此次递归结束,继续下一次递归尝试

另外,棋盘行数在5个以下无解,8个以上耗时太长,建议尝试5或6

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define MAX 15
bool map[MAX][MAX] = {};//棋盘,0代表可跑
int fx[8]={1,2,2,1,-1,-2,-2,-1};  //8个跳转方向 
int fy[8]={2,1,-1,-2,-2,-1,1,2}; 
int pathx[MAX*MAX] = {};//记录跑过的路径
int pathy[MAX*MAX] = {};
//棋盘较大时,尝试时间太长.这里为了方便找到一种结果后立刻返回,修改了下Move的返回值类型 
int Move(int x, int y, int n,int count){
    pathx[count] = x;
    pathy[count] = y;
    count++;
    map[x][y] = false;//跑过路径置false
    if(count==n*n){
        for (int i = 0; i < count-1;i++){
            printf("(%d,%d)-->", pathx[i], pathy[i]);
        }
        printf("(%d,%d)\n", pathx[count-1], pathy[count-1]);
        return 1;
    } 
    int tx, ty;
    for (int i = 0; i < 8;i++){//尝试八个方向
        tx = x + fx[i];
        ty = y + fy[i];
        if (!( tx < 0 || tx > n - 1 || ty < 0 || ty > n - 1|| !map[tx][ty])){
            if(Move(tx, ty, n,count)==1)return 1;
        }
    }
    map[x][y] = true;//递归恢复,继续下一次尝试
    return 0;
}
int main(){
    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            map[i][j] = true;//棋盘初始化
    Move(0, 0, 5,0);//起点为(0,0),棋盘大小5*5
    return 0;
}

样例输出：

(0,0)-->(1,2)-->(2,4)-->(4,3)-->(3,1)-->(1,0)-->(2,2)-->(0,3)-->(1,1)-->(3,0)-->(4,2)-->(3,4)-->(1,3)-->(0,1)-->(2,0)-->(4,1)-->(3,3)-->(1,4)-->(0,2)-->(2,1)-->(4,0)-->(3,2)-->(4,4)-->(2,3)-->(0,4)

本文由 ukuq 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Apr 19, 2019 at 08:40 pm