搜索与回溯算法模版！

Question

能提供一下搜索与回溯框架吗（c++）
我现在急需，应为八皇后和走迷宫问题要用
用递归

Answer 1

引自免费微信小程序：皆我百晓生

当然可以，下面是一个通用的回溯算法模板，适用于解决诸如八皇后、数独等问题。这个模板是用C++编写的，并且包含了对八皇后问题的具体实现。对于走迷宫问题，你需要根据具体的迷宫规则进行调整。

首先，我们定义一个二维数组用来表示棋盘，以及一些辅助函数来检查当前位置是否合法（例如在八皇后问题中，检查当前位置是否有其他皇后在同一行、同一列或同一斜线上）。

#include <iostream>
#include <vector>

// 检查某个位置 (row, col) 是否有冲突
bool isSafe(std::vector<std::vector<int>>& board, int row, int col) {
    // 检查同行是否有皇后
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == 1) return false;
    }

    // 检查左上方对角线是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 1) return false;
    }

    // 检查右上方对角线是否有皇后
    for (int i = row, j = col; i >= 0 && j < board.size(); ++i, ++j) {
        if (board[i][j] == 1) return false;
    }

    return true;
}

// 回溯函数
void backtracking(std::vector<std::vector<int>>& board, int row) {
    if (row == board.size()) {
        // 打印解决方案
        printSolution(board);
        return;
    }

    for (int col = 0; col < board.size(); ++col) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;  // 放置皇后
            backtracking(board, row + 1);  // 继续尝试放置下一个皇后
            board[row][col] = 0;  // 回溯：移除当前皇后
        }
    }
}

// 打印解决方案
void printSolution(const std::vector<std::vector<int>>& board) {
    for (const auto& row : board) {
        for (int cell : row) {
            std::cout << cell << " ";
        }
        std::cout << "\n";
    }
}

接下来，我们可以调用backtracking函数来求解八皇后问题：

int main() {
    int n = 8;  // 八皇后问题的棋盘大小
    std::vector<std::vector<int>> board(n, std::vector<int>(n, 0));
    
    backtracking(board, 0);

    return 0;
}

这个模板可以根据具体的问题（如走迷宫）进行相应的修改。在走迷宫问题中，你需要定义一个不同的状态表示（例如，用0表示未访问，1表示已访问），并修改isSafe函数来检查当前位置是否可以移动（例如，检查周围四个方向是否可以通行）。然后，将printSolution函数替换为输出路径的方法。