C++八皇后问题的最简单算法 |21xrx.com

C++八皇后问题的最简单算法

2023-07-09 12:52:56 深夜i 10 0

C++ 八皇后问题算法最简单

C++八皇后问题是一个经典的问题，旨在找到将八个皇后放置在8x8棋盘上的方法，使得每个皇后都无法在同一行、同一列或同一对角线上相互攻击。

这个问题已经被广泛研究过，有很多不同的解决方法和算法。其中最简单的算法是递归算法，也是最经典的算法。

递归算法实现八皇后问题的思路是：在每一行中放置一个皇后，然后再检查这个皇后是否与之前放置的皇后相互攻击。如果没有，那么继续放置下一行的皇后，直到找到所有解或者无法再放置皇后为止。

下面是一个使用递归算法解决八皇后问题的C++代码：

#include <iostream>
#include <vector>
using namespace std;
bool isSafe(vector<int> &board, int row, int col) {
  for(int i = 0; i < row; i++) {
    if(board[i] == col || abs(row - i) == abs(col - board[i]))
      return false;
    
  }
  return true;
}
void solve(vector<vector<int>> &res, vector<int> &board, int row) {
  if(row == board.size()) {
    res.push_back(board);
    return;
  }
  for(int col = 0; col < board.size(); col++) {
    if(isSafe(board, row, col)) {
      board[row] = col;
      solve(res, board, row + 1);
    }
  }
}
vector<vector<int>> solveNQueens(int n) {
  vector<vector<int>> res;
  vector<int> board(n, -1);
  solve(res, board, 0);
  return res;
}
int main() {
  int n = 8;
  vector<vector<int>> res = solveNQueens(n);
  for(auto board : res) {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        if(board[i] == j)
          cout << "Q ";
         else
          cout << ". ";
        
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

在这个代码中，我们首先定义了一个函数`isSafe`，用于检查当前放置的皇后是否与之前的皇后相互攻击。然后定义了一个递归函数`solve`，用于递归地找到所有合法的解。最后在主函数中调用`solveNQueens`函数来解决八皇后问题，并打印出所有的解。

这个算法虽然简单，但是时间复杂度很高，需要枚举所有的可能性，因此对于大规模的八皇后问题来说可能会非常耗时。因此，在实际中更常用的是其他更高效的算法，比如剪枝算法、遗传算法等。

上一篇: idea打包java可执行jar包

下一篇: Win11下VC++2010安装教程

评论区

相似文章