用C++实现回溯法求马步问题

以下是使用C++实现回溯法求解马步问题的示例代码：

#include <iostream>
using namespace std;

const int N = 10;
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int board[N][N];
int n;

bool check(int x, int y) {
    // 判断坐标是否越界
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    // 判断该位置是否已经被访问过
    if (board[x][y] != -1) return false;
    return true;
}

bool dfs(int x, int y, int step) {
    board[x][y] = step;
    if (step == n * n) return true;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (check(nx, ny)) {
            if (dfs(nx, ny, step + 1)) return true;
        }
    }
    board[x][y] = -1;
    return false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = -1;
        }
    }
    dfs(0, 0, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

在上述代码中，我们首先定义了一个`check()`函数，用来判断当前位置是否可以走。然后，我们定义了一个`dfs()`函数，用来实现回溯法的搜索过程。在`dfs()`函数中，我们首先将当前位置标记为已访问，然后按照马的移动规则依次尝试走下一步。如果走到了最后一个格子，那么表示已经找到了一条路径，返回`true`。如果没有找到，就需要回溯到上一个位置，重新选择下一步走向，直到找到一条路径为止。最后，我们输出找到的路径。

在主函数中，我们首先读入棋盘大小`n`，然后将棋盘上所有的位置初始化为-1，代表未访问过。接着，我们调用`dfs()`函数开始搜索，从$(0,0)$位置开始遍历，遍历的步数从1开始计算。最后，我们输出遍历的结果。

以上就是使用C++实现回溯法求解马步问题的示例代码。