Application of C++ recursive function in backtracking algorithm?

Recursive functions solve problems by depth-first searching the decision tree in the backtracking algorithm: the function calls itself and explores the branches of the decision tree. In response to the problem, the function will continue to explore the tree structure deeply and backtrack after making wrong decisions. Practical case: In the eight-queen problem, the function recursively places the queens and backtracks to undo the incorrectly placed queens, and finally finds a solution that meets the requirements.

C Application of recursive function in backtracking algorithm

The backtracking algorithm is an algorithm based on depth-first search, which explores deeply on the decision tree , and backtracking to solve problems after making poor decisions. Recursive functions play a crucial role in backtracking algorithms, allowing the function to call itself to explore the branches of a decision tree.

Code:

In C, we can use recursive functions to implement the backtracking algorithm, such as solving the eight queens problem:

#include <iostream>
#include <vector>
using namespace std;

// 八皇后问题
bool solveNQueens(vector<vector<int>>& board, int n, int row) {
  if (row == n) {
    return true; // 找到一个解
  }

  for (int col = 0; col < n; col++) {
    if (isSafe(board, row, col)) {
      board[row][col] = 1;  // 放置皇后

      if (solveNQueens(board, n, row + 1)) {
        return true; // 在该分支中找到解
      }

      board[row][col] = 0;  // 回溯：移除皇后
    }
  }

  return false; // 未找到解
}

bool isSafe(vector<vector<int>>& board, int row, int col) {
  for (int i = 0; i < row; i++) {
    if (board[i][col] == 1) {
      return false; // 列冲突
    }
    if (board[i][col - row + i] == 1) {
      return false; // 左对角线冲突
    }
    if (board[i][col + row - i] == 1) {
      return false; // 右对角线冲突
    }
  }
  return true; // 该位置安全
}

int main() {
  int n;
  cout << "请输入棋盘大小：";
  cin >> n;

  vector<vector<int>> board(n, vector<int>(n, 0));

  if (solveNQueens(board, n, 0)) {
    cout << "找到解：\n";
    for (auto& row : board) {
      for (auto& cell : row) {
        cout << cell << " ";
      }
      cout << "\n";
    }
  } else {
    cout << "未找到解\n";
  }

  return 0;
}

Practical case:

The eight queens problem is a well-known combinatorial optimization problem. It requires placing 8 queens on an 8x8 chessboard so that they do not attack each other. This code demonstrates how to use a recursive function and a backtracking algorithm to solve this problem and output the solution in a checkerboard format.

The above is the detailed content of Application of C++ recursive function in backtracking algorithm?. For more information, please follow other related articles on the PHP Chinese website!