C++骑士游历问题（马踏棋盘）解析

简介

骑士游历问题，又称马踏棋盘问题，属于图论中的路径问题。问题描述：在一个 n*n 的棋盘上，放置一个马的棋子，从任意一个位置出发，按照马的走法，遍历所有的棋盘。不可重复经过。

解题思路

递归回溯法

定义

首先定义一个二维棋盘 board 存储马在棋盘上的路径。board[i][j]的值为k表示是第 k 步走到了位置 (i, j)。对于第一步，令 board[i][j]=1。

使用递归回溯法，对于当前位置 (x,y)，做以下几个步骤：

1. 判断此位置是否越界，如果越界，则返回 false。
2. 判断此位置是否已经走过，如果走过，则返回 false。
3. 如果当前步数已经到达 n*n，表示完成遍历，返回 true。
4. 对当前位置各个方向上的下一步位置递归调用步骤 1~3，如果返回值为 true，表示此方向可以到达，更新 board 数组，在把当前位置返回到它之前的步骤栈中。

bool knight_travel(int x, int y, int step, int n, vector<vector<int>>& board){
    // 判断越界情况
    if (x < 0 || x >= n || y < 0 || y >= n){
        return false;
    }
    // 判断已经走过的情况
    if (board[x][y] != 0){
        return false;
    }
    // 当前步数已经到达 n*n，表示完成遍历
    if (step == n * n){
        return true;
    }
    // 对当前位置各个方向上的下一步位置递归调用步骤 1~3
    int next_x;
    int next_y;
    for (int i = 0; i < 8; i++){
        next_x = x + dx[i];
        next_y = y + dy[i];
        if (knight_travel(next_x, next_y, step + 1, n, board)){
            board[next_x][next_y] = step + 1;
            return true;
        }
    }
    // 没有找到可行解，返回 false
    return false;
}

示例

以 n = 8 为例，输出一个 8*8 的棋盘，其中 1 表示起始点，64 表示终点，其余数字表示到达此位置的步数。

int main(){
    int n = 8;
    vector<vector<int>> board(n, vector<int>(n, 0));
    int start_x = 0;
    int start_y = 0;
    board[start_x][start_y] = 1;
    if (knight_travel(start_x, start_y, 1, n, board)){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cout << board[i][j] << "\t";
            }
            cout << endl;
        }
    }
    return 0;
}

输出结果为：

1       38      59      48      53      28      43      62
58      47      2       37      60      63      52      27
39      54      49      58      45      26      29      42
46      57      36      3       44      61      26      25
55      40      57      50      23      24      41      30
34      45      56      35      4       31      22      19
59      22      41      62      11      20      9       32
44      33      24      17      56      51      18      5

Warnsdorff算法

定义

Warnsdorff算法是一种贪心算法，其主要思想是每次都优先选择下一步可以到达空位最少的位置。

算法具体实现步骤：

1. 从起始位置开始，将当前可行位置的下一步空位数量预先计算出来，并排序（升序），选择空位最少的位置为下一步走的位置。
2. 访问下一步位置，将当前可行位置的下一步空位数量重新计算，按照空位数量排序后，选择空位最少的位置为下一步走的位置。依次类推直到遍历完整个棋盘。

vector<int> dx = {1, 1, 2, 2, -1, -1, -2, -2};
vector<int> dy = {2, -2, 1, -1, 2, -2, 1, -1};

bool within_board(int x, int y, int n){
    return (x >= 0 && x < n) && (y >= 0 && y < n);
}

bool get_next_move(int x, int y, int n, vector<vector<bool>>& visited, vector<pair<int,int>>& next_moves){
    for (int i = 0; i < 8; i++){
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        int count = 0;
        if (within_board(next_x, next_y, n) && !visited[next_x][next_y]){
            for (int j = 0; j < 8; j++){
                int t_x = next_x + dx[j];
                int t_y = next_y + dy[j];
                if (within_board(t_x, t_y, n) && !visited[t_x][t_y]){
                    count++;
                }
            }
            next_moves.push_back({count, i});
        }
    }
    if (next_moves.empty()){
        return false;
    }
    sort(next_moves.begin(), next_moves.end());
    return true;
}

void print_board(vector<vector<int>>& board){
    int n = board.size();
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cout << board[i][j] << "\t";
        }
        cout << endl;
    }
}

void knight_travel_w(vector<vector<int>>& board){
    int n = board.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    int x = 0;
    int y = 0;
    int step = 1;
    visited[x][y] = true;
    board[x][y] = step;
    while (step < n * n){
        vector<pair<int,int>> next_moves;
        if (!get_next_move(x, y, n, visited, next_moves)){
            // 无解情况
            return;
        }
        auto next_move = next_moves[0];
        int next_x = x + dx[next_move.second];
        int next_y = y + dy[next_move.second];
        step++;
        visited[next_x][next_y] = true;
        board[next_x][next_y] = step;
        x = next_x;
        y = next_y;
    }
}

示例

以 n = 8 为例，输出一个 8*8 的棋盘，其中 1 表示起始点，64 表示终点，其余数字表示到达此位置的步数。

int main(){
    int n = 8;
    vector<vector<int>> board(n, vector<int>(n, 0));
    knight_travel_w(board);
    print_board(board);
    return 0;
}

输出结果为：

1       58      45      34      19      8       31      50
44      33      2       57      32      49      20      9
59      46      35      18      7       30      51      38
42      43      56      3       50      61      10      21
27      60      47      36      53      4       37      52
16      41      22      55      62      17      24      11
39      28      63      48      15      6       23      40
64      25      40      29      54      43      12      5

总结

两种方法的时间复杂度都是指数级别的，对于比较大的 n 值，都会出现栈溢出等问题，因此需要优化算法，使其不再具有指数级别的复杂度。