C++递归实现马踏棋盘算法详解

问题原理与思路

马踏棋盘是经典的组合数学问题。假设棋盘大小为 X × Y，我们需要找到一条长度为 X * Y 的路径，使得马按照“日”字形移动规律覆盖所有格子。

算法的核心逻辑如下：

1. 状态记录：使用二维数组 chess[Y][X] 标记当前格子的访问序号，未访问为0。
2. 试探方向：定义8个可能的跳跃方向，通常按顺时针排列，依次尝试。
3. 递归回溯：
     - 若当前点有合法下一步，标记步数并递归进入下一层；
     - 若递归返回失败或无路可走，则撤销当前步标记（置0），尝试下一个方向；
     - 当已覆盖总格子数时，说明找到解。

代码实现解析

以下代码实现了一个5x5的棋盘测试案例。主要包含三个部分：方向判定、递归探索结果输出。

第1步：定义方向判定函数 Next

该函数根据给定的8个方向索引，计算偏移量并检查目标位置是否在棋盘内且未被访问。若符合条件，则更新坐标指针并返回1，否则返回0。

第2步：执行递归探索 Explore

这是核心算法。counter 记录当前步数，chess[y][x] 记录路径。函数尝试每个方向，如果找到一个有效位置，就递归调用自身。如果递归返回假，或者所有方向都无效，则执行回溯操作：将当前格子复位为0，步数减1，并尝试其他方向。

第3步：输出结果与计时 ShowResult & main

初始化起始点后调用探索函数。成功找到路径后，遍历数组打印出每格的访问顺序。同时使用 clock() 记录算法耗时。

#include<iostream>
#include<time.h>
using namespace std;

#define X 5
#define Y 5

int chess[Y][X] = {0};
int counter = 0;

// 寻找下一跳的方向
int Next(int* x, int* y, int where) {
    switch(where) {
        case 0:
            if(*x+1<X && *y-2>=0 && chess[*y-2][*x+1]==0) {
                *x+=1; *y-=2; return 1;
            }
            break;
        case 1:
            if(*x+2<X && *y-1>=0 && chess[*y-1][*x+2]==0) {
                *x+=2; *y-=1; return 1;
            }
            break;
        case 2:
            if(*x+2<X && *y+1<Y && chess[*y+1][*x+2]==0) {
                *x+=2; *y+=1; return 1;
            }
            break;
        case 3:
            if(*x+1<X && *y+2<Y && chess[*y+2][*x+1]==0) {
                *x+=1; *y+=2; return 1;
            }
            break;
        case 4:
            if(*x-1>=0 && *y+2<Y && chess[*y+2][*x-1]==0) {
                *x-=1; *y+=2; return 1;
            }
            break;
        case 5:
            if(*x-2>=0 && *y+1<Y && chess[*y+1][*x-2]==0) {
                *x-=2; *y+=1; return 1;
            }
            break;
        case 6:
            if(*x-2>=0 && *y-1>=0 && chess[*y-1][*x-2]==0) {
                *x-=2; *y-=1; return 1;
            }
            break;
        case 7:
            if(*x-1>=0 && *y-2>=0 && chess[*y-2][*x-1]==0) {
                *x-=1; *y-=2; return 1;
            }
            break;
    }
    return 0;
}

// 递归回溯探索
int Explore(int x, int y) {
    int x1=x, y1=y;
    int flag, where=0;
    
    counter++;
    chess[y][x] = counter;
    
    // 如果已经走遍全图，返回成功
    if(counter == X * Y) {
        return 1;
    }
    
    // 尝试第一个方向
    flag = Next(&x1, &y1, where);
    while(flag==0 && where<7) {
        where++; 
        flag = Next(&x1, &y1, where);
    }
    
    // 只要有路可选，就继续深入或回溯
    while(flag) {
        if(Explore(x1, y1)==1) {
            return 1;
        } else {
            // 此路不通，回溯
            x1=x; y1=y;
            where++;
            flag = Next(&x1, &y1, where);
            while(flag==0 && where<7) {
                where++;
                flag = Next(&x1, &y1, where);
            }
        }
    }
    
    // 彻底无路可走，回溯到上一层
    if(flag==0) {
        chess[y][x] = 0;
        counter--;
    }
    return 0;
}

void ShowResult() {
    for(int i=0; i<Y; i++) {
        for(int j=0; j<X; j++) {
            cout.width(4);
            cout << chess[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int start = clock();
    // 从 (2, 1) 开始尝试
    int result = Explore(2, 1);
    int end = clock();
    
    if(result) {
        ShowResult();   
    } else {
        cout << "have no path!" << endl; 
    }
    cout << "spend time: " << (end-start)/CLOCKS_PER_SEC << " s" << endl;
    return 0;
}

总结

马踏棋盘问题通过简单的回溯算法即可解决，但在较大棋盘上复杂度会呈指数级增长，因此对于8x8甚至更大规模的棋盘，通常需要引入启发式算法优化。以上就是C++实现马踏棋盘的详细内容，更多关于骑士周游算法的资料请关注本站其它相关文章！