骑士游历问题 C++ 解法：回溯算法实现

骑士游历问题是一个经典的回溯算法问题，其目标是找到一个骑士的游历路径，使其能够经过棋盘上的每个格子，且每个格子只经过一次。

以下是一个用 C++ 实现的骑士游历问题的解决方案：

#include <iostream>
#include <vector>

// 定义棋盘的大小
#define N 8

// 定义骑士的移动方向
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

// 检查下一个位置是否合法
bool isValid(int x, int y, std::vector<std::vector<int>>& board) {
    return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1);
}

// 使用回溯算法求解骑士游历问题
bool solveKnightTour(int x, int y, int moveCount, std::vector<std::vector<int>>& board) {
    // 所有的格子都已经经过，返回true
    if (moveCount == N * N)
        return true;

    // 尝试骑士的8个移动方向
    for (int i = 0; i < 8; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (isValid(nextX, nextY, board)) {
            // 标记当前位置已经经过
            board[nextX][nextY] = moveCount;

            // 递归求解下一个位置
            if (solveKnightTour(nextX, nextY, moveCount + 1, board))
                return true;

            // 回溯，取消当前位置的标记
            board[nextX][nextY] = -1;
        }
    }

    return false;
}

int main() {
    // 初始化棋盘
    std::vector<std::vector<int>> board(N, std::vector<int>(N, -1));

    // 设置起始位置
    int startX = 0;
    int startY = 0;
    board[startX][startY] = 0;

    // 求解骑士游历问题
    if (solveKnightTour(startX, startY, 1, board)) {
        // 输出解决方案
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                std::cout << board[i][j] << '	';
            }
            std::cout << std::endl;
        }
    } else {
        std::cout << 'No solution found!' << std::endl;
    }

    return 0;
}

在上述代码中，我们首先定义了一个 8x8 的棋盘和骑士的 8 个移动方向。然后，我们使用回溯算法实现了solveKnightTour函数来求解骑士游历问题。在该函数中，我们首先检查下一个位置是否合法，如果合法，则将其标记为已经经过，然后递归求解下一个位置。如果递归返回 true，则说明找到一条解决方案，否则，我们回溯取消当前位置的标记。最后，在主函数中，我们设置起始位置为 (0, 0)，然后调用solveKnightTour函数来求解问题，并输出解决方案。

希望对你有帮助！